[科普中国]-约瑟夫斯问题

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

历史这个问题是以弗拉维奥·约瑟夫命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。1

解法比较简单的做法是用循环单链表模拟整个过程，时间复杂度是O(n*m)。如果只是想求得最后剩下的人，则可以用数学推导的方式得出公式。且先看看模拟过程的解法。2

Python版本# -*- coding: utf-8 -*- class Node(object): def __init__(self, value): self.value = value self.next = Nonedef create_linkList(n): head = Node(1) pre = head for i in range(2, n+1): newNode = Node(i) pre.next= newNode pre = newNode pre.next = head return headn = 5 #总的个数m = 2 #数的数目if m == 1: #如果是1的话，特殊处理，直接输出 print (n) else: head = create_linkList(n) pre = None cur = head while cur.next != cur: #终止条件是节点的下一个节点指向本身 for i in range(m-1): pre = cur cur = cur.next print (cur.value) pre.next = cur.next cur.next = None cur = pre.next print (cur.value)C++版本#include using namespace std;typedef struct _LinkNode { int value; struct _LinkNode* next;} LinkNode, *LinkNodePtr;LinkNodePtr createCycle(int total) { int index = 1; LinkNodePtr head = NULL, curr = NULL, prev = NULL; head = (LinkNodePtr) malloc(sizeof(LinkNode)); head->value = index; prev = head; while (--total > 0) { curr = (LinkNodePtr) malloc(sizeof(LinkNode)); curr->value = ++index; prev->next = curr; prev = curr; } curr->next = head; return head;}void run(int total, int tag) { LinkNodePtr node = createCycle(total); LinkNodePtr prev = NULL; int start = 1; int index = start; while (node && node->next) { if (index == tag) { printf("\n%d", node->value); if (tag == start) { prev = node->next; node->next = NULL; node = prev; } else { prev->next = node->next; node->next = NULL; node = prev->next; } index = start; } else { prev = node; node = node->next; index++; } }}int main() { run(5, 999999); return 0;}本词条内容贡献者为:

杨晓红 - 副教授 - 西南大学