1 约瑟夫环问题.docx

约瑟夫环问题一、C语言递归实现问题描述：假设下标从0开始，0、1、2 m-1共m个人，从1开始报数，报到k则此人从环中退出，问最后剩下的一个人的编号是多少？解析：现在假设m=10 ： 0 1 2 3 4 5 6 7 8 9， k=3第一个人出列后的序列为： 0 1 3 4 5 6 7 8 9即: 3 4 5 6 7 8 9 0 1 （*）我们把该式转化为: 0 1 2 3 4 5 6 7 8 (*)则你会发现: （(*)+3）%10则转化为(*)式了也就是说，我们求出9个人中第9次出环的编号，最后进行上面的转换就能得到10个人第10次出环的编号了。设f(m, k, i)为m个人的环，报数为k，第i个人出环的编号，则f(10,3,10)是我们要的结果。当i = 1时， f(m, k, i) = (k-1)%m当i != 1时， f(m, k, i)= ( f(m-1,k,i-1)+k )%m代码：#include int fun(int m,int k,int i) if(i=1) return (k-1)%m; else return (fun(m-1,k,i-1)+k)%m; int main(int argc, char *argv)int i; for(i=1;i0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。简化问题描述：n个人（编号0(n-1)，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。思路：容易想到的就是用环链表来做，构建一个环链表，每个结点的编号为0, 1, . n-1。每次从当前位置向前移动m-1步，然后删除这个结点。最后剩下的结点就是胜利者。给出两种方法实现，一种是自定义链表操作，另一种用是STL库的单链表。不难发现，用STL库可以提高编写速度。1. structListNode2. 3. intnum;/编号4. ListNode*next;/下一个注：这里用ListNode来定义，只有在c+中可以，c里不可以5. ListNode(intn=0,ListNode*p=NULL)6. num=n;next=p;7. ;8. 9. /自定义链表实现10. intJosephusProblem_Solution1(intn,intm)11. 12. if(n1|m1)13. return-1;14. 15. ListNode*pHead=newListNode();/头结点16. ListNode*pCurrentNode=pHead;/当前结点17. ListNode*pLastNode=NULL;/前一个结点18. unsignedi;19. 20. /构造环链表21. for(i=1;inext=newListNode(i);24. pCurrentNode=pCurrentNode-next;25. 26. pCurrentNode-next=pHead;27. 28. /循环遍历29. pLastNode=pCurrentNode;30. pCurrentNode=pHead;31. 32. while(pCurrentNode-next!=pCurrentNode)33. 34. /前进m-1步35. for(i=0;inext;39. 40. /删除报到m-1的数41. pLastNode-next=pCurrentNode-next;42. deletepCurrentNode;43. pCurrentNode=pLastNode-next;44. 45. /释放空间46. intresult=pCurrentNode-num;47. deletepCurrentNode;48. 49. returnresult;50. 51.52. /使用标准库53. intJosephusProblem_Solution2(intn,intm)54. 55. if(n1|m1)56. return-1;57. 58. listlistInt;59. unsignedi;60. /初始化链表61. for(i=0;in;i+)62. listInt.push_back(i);63. 64. list:iteratoriterCurrent=listInt.begin();65. while(listInt.size()1)66. 67. /前进m-1步68. for(i=0;im-1;i+)69. 70. if(+iterCurrent=listInt.end()71. iterCurrent=listInt.begin();72. 73. /临时保存删除的结点74. list:iteratoriterDel=iterCurrent;75. if(+iterCurrent=listInt.end()76. iterCurrent=listInt.begin();77. /删除结点78. listInt.erase(iterDel);79. 80. 81. return*iterCurrent;82. 上述方法的效率很低，其时间复杂度为O(mn)。当n和m很大时，很难在短时间内得出结果。不过好处就是可以给出n个人出圈的次序。只要在删除前保存一下即可。下面利用数学推导，如果能得出一个通式，就可以利用递归、循环等手段解决。下面给出推导的过程：（1）第一个被删除的数为 (m - 1) % n。（2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, .,k - 3, k - 2。做一个简单的映射。k -0 k+1 - 1 k+2 - 2 . . k-2 - n-2这是一个n -1个人的问题，如果能从n - 1个人问题的解推出 n 个人问题的解，从而得到一个递推公式，那么问题就解决了。假如我们已经知道了n -1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为 (x + k) % n。其中k等于m % n。代入(x + k) % n (x + (m % n)%n (x%n + (m%n)%n)%n (x%n+m%n)%n (x+m)%n（3）第二个被删除的数为(m - 1) % (n - 1)。（4）假设第三轮的开始数字为o，那么这n - 2个数构成的约瑟夫环为o, o + 1, o + 2,.o - 3, o - 2.。继续做映射。 o - 0 o+1 - 1 o+2 - 2 . . o-2 - n-3这是一个n - 2个人的问题。假设最后的胜利者为y，那么n -1个人时，胜利者为 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)要得到n - 1个人问题的解，只需得到n - 2个人问题的解，倒推下去。只有一个人时，胜利者就是编号0。下面给出递推式： f 1 = 0; f i = ( f i -1 + m) % i; (i1)有了递推公式，实现就非常简单了，给出循环的两种实现方式。再次表明用标准库的便捷性。1. intJosephusProblem_Solution3(intn,intm)2. 3. if(n1|m1)4. return-1;5. 6. int*f=newintn+1;7. f0=f1=0;/f0其实用不到的8. 9. for(unsignedi=2;i=n;i+)10. fi=(fi-1+m)%i;/按递推公式进行计算11. 12. intresult=fn;13. deletef;14. 15.