大家好，我是讯享网，很高兴认识大家。

问题由来：

        在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

一般形式：

        N个人围成一个圈，编号为1到N，从1号开始报数，报数为M的人出局；其他人继续围成圈，从出局人的下一个开始重新报数，报到M的人又出局。直到剩下最后一个人。

可以用数组或者链表来模拟这个报数的过程，如下是数组实现的C++代码：

const int maxn = 10000; void ArrayJose() { bool jose[maxn] = {0}; //设置一个数组来模拟N个人 int m_count = 0; //记录当前报的数 int i = 0; //记录当前遍历的是数组的第几个元素 int out_count = 0; //记录当前出局的人数 int n, m; cin >> n >> m; do { ++i; if (i > n) //所有人报数完后从头开始报数 i = 1; if (!jose[i]) //若数组元素为0，即这个人没出局 m_count++; if (m_count == m) { //报数为m的人出局 m_count = 0; //重新开始报数 cout << i << " "; //输出出局人编号 jose[i] = 1; //将这个人所在位置标记为出局：1 out_count++; //出局人数加1 } } while (out_count != n); }

讯享网

以下是C++的循环单链表方式：

讯享网struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; struct Node { int element; Position next; }; List MakeCircleList(int n) {     List jose = NULL;     int i = 0;     Position node, rear;     for (i = 1; i <= n; i++) {         node = (struct Node *)malloc(sizeof(struct Node));         if (node == NULL) {             cout << "malloc failed." << endl;             return NULL;         }         node->element = i;         if (jose == NULL) {             jose = node;         }         else {             rear->next = node;         }         rear = node;     }     rear->next = jose;     return jose; } void CircleListJose(int n, int m, List jose) {     int m_count = 0, out_count = 0;     int i;     Position q, p = jose;     q = p;     while (p->next != p) {         for (i = 1; i < m; ++i) {             q = p;             p = p->next;         }         Position start = p->next;         cout << p->element << " ";         q->next = p->next;         free(p);         p = start;     }     cout << p->element << endl; } 

          以上的两种方式的思想都是一样的：要模拟所有人报数并出局的整个过程。这种思想的复杂度比较大，为 O(mn)。通过数学方式可以提高算法的效率。可以将 问题描述改为： n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

        注意这里的方法没有将每次报数人的编号计算出来，而是仅仅求出了胜利者的编号，下面算法的复杂度为O(n)。

        当第一个人出列后（这个人的编号一定是（m - 1）% n，剩下的n - 1 个人重新构成了一个新的约瑟夫环（这个环以k = m % n开始报数）：

k，k+1，k+2，……，n-2，n-1，0，1，……，k-2。

       将这n-1个人依次重新编号为0，1，2，……，n-1：

k   --->  0，

k+1  --->   1，

k+2  ---->   2，

讯享网

……

k-2 --->   n - 2

即转换映射为 x   --->  (n + x - k - 1) % n   ==  (x - k - 1) % n，反向的转换关系为：  x  <---  (x + k + 1 - n) % n ==  (x + k + 1) % n 

         这些人继续从0号开始报数，那么，如果这n-1个人子问题的最后胜利者编号为f(n)。如果设n个人时胜利者编号为f(n - 1)的话，那么可以得到递推关系式：

f(n)  = (f(n - 1)  + k  + 1) % n;   将 k = （m - 1）% n 代入， f(n) = ( f(n - 1) + (m - 1) % n + 1) % n = ( f(n - 1) + m) % n

         也就是说，如果求得了n-1个人的胜利者根据递推关系式就可以求得n个人的胜利者，那么n-1个人的胜利者就通过求n-2个人的胜利者来求，因此这是递归过程。

代码实现如下：

int main(void) { int n, m,i, f[20]={0}; scanf("%d %d",&n,&m); for(i=2;i<=n;i++) { f[i]=(f[i-1]+m)%i; printf("%d个人报数，报到%d的出列，最后的胜者下标为%d\n", i,m,f[i]); } printf("The winner is %d\n", f[n]+1); system("pause"); } 

优化后代码：

讯享网int main(void) { int n, m,i, s=0; scanf("%d %d",&n,&m); for(i=2;i<=n;i++) { s=(s+m)%i; } printf("The winner is %d\n", s + 1); } 

-----------------------------------------------------------------------分割线-----------------------------------------------------------------------------------

注意以下使用的变量含义与上述没必要联系。

一道ACM的约瑟夫变形题：

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. 

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.