资源描述：
《1 约瑟夫环问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、约瑟夫环问题一、C语言——递归实现问题描述：假设下标从0开始，0、1、2…m-1共m个人，从1开始报数，报到k则此人从环中退出，问最后剩下的一个人的编号是多少？解析：现在假设m=10：0123 456789， k=3第一个人出列后的序列为：013456789即:345678901（*）我们把该式转化为:012345678(**)则你会发现:（(**)+3）%10则转化为(*)式了也就是说，我们求出9个人中第9次出环的编号，最后进行上面的转换就能得到10个人第10次出环的编号了 。设f(m,k,i)为m个人的环，报数为k，第i个人出
2、环的编号，则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代码：#includeintfun(intm,intk,inti){if(i==1)return(k-1)%m;elsereturn(fun(m-1,k,i-1)+k)%m;}intmain(intargc,char*argv[]){inti;for(i=1;i<=10;i++)printf("第%2d次出环：%2d",i,fun(10,3,i));
3、return0;}结果：这里要注意：看清编号起始值、报数起始值，以及报数起始位置。根据具体情况来推算递归表达式以及初始位置。编号最好重新设置成从0开始。报数可以从1开始：递推公式如上所示也可以从0开始：将上述递推公式中的k改为k+1二、C++实现原问题描述：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 简化问题描述：n个人（
4、编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 思路：容易想到的就是用环链表来做，构建一个环链表，每个结点的编号为0,1,...n-1。每次从当前位置向前移动m-1步，然后删除这个结点。最后剩下的结点就是胜利者。给出两种方法实现，一种是自定义链表操作，另一种用是STL库的单链表。不难发现，用STL库可以提高编写速度。1.struct ListNode 2.{ 3. int num; //编号 4. ListNode *next; //下一个 注：
5、这里用ListNode 来定义，只有在c++中可以，c里不可以5. ListNode(int n = 0, ListNode *p = NULL) 6. { num = n; next = p;} 7.}; 8. 9.//自定义链表实现 10.int JosephusProblem_Solution1(int n, int m) 11.{ 12. if(n < 1
6、
7、 m < 1) 13. return -1;14. 15. ListNode *pHead = new Li
8、stNode(); //头结点 16. ListNode *pCurrentNode = pHead; //当前结点 17. ListNode *pLastNode = NULL; //前一个结点 18. unsigned i; 19. 20. //构造环链表 21. for(i = 1; i < n; i++) 22. { 23. pCurrentNode->next = new ListNode(i); 24. pCurrentNo
9、de = pCurrentNode->next; 25. } 26. pCurrentNode->next = pHead; 27. 28. //循环遍历 29. pLastNode = pCurrentNode; 30. pCurrentNode = pHead; 31. 32. while(pCurrentNode->next != pCurrentNode) 33. { 1. //前进m - 1步 2. for(i = 0; i < m
10、-1; i++) 3. { 4. pLastNode = pCurrentNode; 5. pCurrentNode = pCurrentNode->next; 6.
