EEPW论坛

约瑟夫环问题：一圈共有N个人，开始报数，报道M的人自杀，然后重新开始报数，问到最后自杀的人是谁？

如图：内环表示人的排列的环，外环表示自杀顺序；上面N=41；M=3

最普通的办法就是模拟整个过程：建一个bool数组，true表示此人还活着，false表示已经自杀，可以模拟整个实现

1. int main()  

2. {  

3.     int N;//人的总数  

4.     int M;//间隔多少人  

5.   

6.     cin >> N;  

7.     cin >> M;  

8.   

9.     bool *p = new bool[N+1]; //[1...N]为true表示此人还活着  

10.     for (int i=1; i<=N; i++)  

11.     {  

12.         p[i] = true;  

13.     }  

14.   

15.     int count = 0;//统计自杀的人数  

16.   

17.     //i用来表示循环，j用来计算是不是第N个人  

18.     for (int i=1, j=0; ; i++)  

19.     {  

20.         if (p[i])//此人还活着  

21.         {  

22.             j++;  

23.             if (j==M)  

24.             {  

25.                 p[i] = false;  

26.                 j = 0;  

27.                 count++;//自杀人数  

28.             }  

29.   

30.             if (count==N)  

31.             {  

32.                 cout << "最后自杀的人是" << i << endl;  

33.                 break;  

34.             }  

35.         }  

36.   

37.         if (i==N)  

38.         {  

39.             i = 0;  

40.         }  

41.     }  

42.     delete[] p;  

43.     system("pause");  

44.     return 0;  

45. }  

模拟整个过程，复杂度为o(mn).可以用数学方法来求解；

把问题重新描述下：N个人（编号0~（N-1））,从0开始报数，报道M-1的自杀，剩下的人继续从0开始报数，求最后自杀人的编号：

第一个自杀的人是(M-1)%N，例如上图中，41个人中，报到3的人自杀，则第一个自杀的编号是（3-1）%41=2；编号（M-1)%N自杀后，剩下的人排列如下：

有人自杀后，下一个位置又从0开始报数，

问题变为了n-1个人，报道m-1的人自杀，问题规模减小，这样一直下去，最后剩下编号为0的人，用函数表示为：

F(1)=0

当有2个人的时候，报道M-1的人自杀，最后自杀的人是谁，应该是在只有一个人的时候，报数时得到自杀的序号上加M,,因为报到

M-1的人已经自杀了，只剩下2个人，另一个自杀者就是最后的自杀者，用函数表示：

F(2)=F(1)+M

可以得到的递推工时：

F(i=F(i-1)+M

因此可能会超出总人数，所以求模

F(i)=(F(i-1)+M)%i