约瑟夫问题的N种解法

0x55AA

1 问题的历史以及不同的版本
1.1
    约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。

1.2
    17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒.

1.3
    有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号 开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样， 直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编
号。

1.4
    编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。编程打印出列顺序。

2 问题的解法
2.1 数组解法
    建立一个数组并且初始化所有的元素为1，然后开始遍历数组，遇到符合条件的就把数组中对用的元素设置为0，并且在下次循环的时候不把0包括在内。
程序如下所示：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void main()
   
5. {
   
6.     cout<<"Please input the total number n and selected number m"<<endl;
   
7.     int n,m;
   
8.     cin>>n>>m;
   
9.     if( n<2 || m<1 )
   
10.     {
    
11.         cout<<"n is at least equal to 2 and m must bigger than 0"<<endl;
    
12.         cin>>n>>m;
    
13.     }
    
14. 
    
15.     int* pArr = new int[n];
    
16.     for(int i=0;i<n;i++)
    
17.         pArr[i ] = i+1;
    
18. 
    
19.     int i=0;
    
20.     int j=0;
    
21.     int k=0;
    
22.     while(k<n)
    
23.     {
    
24.         if( pArr[i ] !=0 )
    
25.             j++;
    
26.         if( j==m )
    
27.         {
    
28.             j=0;
    
29.             cout<<pArr[i ]<<"   ";
    
30.             pArr[i ]=0;
    
31.             k++;
    
32.         }
    
33.         if(i<n-1)
    
34.             i++;
    
35.         else
    
36.             i=0;
    
37.     }
    
38. 
    
39.     delete[] pArr;
    
40. }

复制代码

2.2 循环链表解法
    这个是最显而易见的想法，遇到符合条件的节点就将其删除并且输出对应的编号
程序如下：

1. #include <iostream>
   
2. #include "Link.h"
   
3. using namespace std;
   
4. 
   
5. void main()
   
6. {
   
7.     cout<<"Please input the total number n and the selected m"<<endl;
   
8.     int n,m;
   
9.     cin>>n>>m;
   
10.     if( n<2 || m<1)
    
11.     {
    
12.         cout<<"n is at least equal to 2 and m is must bigger than 0"<<endl;
    
13.         cin>>n>>m;
    
14.     }
    
15.     Node *head = InitLink(n);
    
16.     if(head == NULL)
    
17.     {
    
18.         cout<<"Init linklist failed"<<endl;
    
19.         return;
    
20.     }
    
21. 
    
22.     int k=0;
    
23.     int i=0;
    
24.     Node *ptr = head;
    
25.     Node *p = NULL;
    
26.     while(k<n)
    
27.     {
    
28.         if(i<m-1)
    
29.         {
    
30.             i++;
    
31.             p = ptr;
    
32.             ptr = ptr->next;
    
33.         }
    
34.         else
    
35.         {
    
36.             cout<<ptr->nId<<"   ";
    
37.             p->next = ptr->next;
    
38.             Node* ptmp = ptr;
    
39.             ptr = ptr->next;
    
40.             
    
41.             delete ptmp;
    
42.             ptmp = NULL;
    
43.             k++;
    
44.             i=0;
    
45.         }
    
46.     }   
    
47. }

复制代码

2.3   递推解法
    n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i ]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i ]=(f[i-1]+m)%i; (i>1)
实现程序如下所示：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void main()
   
5. {
   
6.     int n;
   
7.     int m;
   
8.     cout<<"Please int n for total number and m for selected number"<<endl;
   
9.     cin>>n>>m;
   
10.     if(n<2 || m<=0)
    
11.     {
    
12.         cout<<"n is at least equal to 2 and m must be bigger than 0"<<endl;
    
13.         cin>>n>>m;
    
14.     }
    
15. 
    
16.     int s = 0;
    
17.     for(int i=2;i<=n;i++)
    
18.         s = (s + m) % i;
    
19.     cout<<"The left number is(0 based): "<<s<<endl;
    
20. }

复制代码