1 约瑟夫环问题.docxVIP

约瑟夫环问题一、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 stdio.hint fun(intm,intk,inti){if(i==1)return (k-1)%m;elsereturn (fun(m-1,k,i-1)+k)%m; }int main(intargc, char *argv[]){inti;for(i=1;i=10;i++)printf(第%2d次出环：%2d\n,i,fun(10,3,i));return 0;}结果：二、C++实现原问题描述：设有编号为1，2，……，n的n(n0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。??简化问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。?思路：容易想到的就是用环链表来做，构建一个环链表，每个结点的编号为0, 1, ... n-1。每次从当前位置向前移动m-1步，然后删除这个结点。最后剩下的结点就是胜利者。给出两种方法实现，一种是自定义链表操作，另一种用是STL库的单链表。不难发现，用STL库可以提高编写速度。struct?ListNode??{??????int?num;????????//编号??????ListNode?*next;?//下一个??注：这里用ListNode?来定义，只有在c++中可以，c里不可以????ListNode(int?n?=?0,?ListNode?*p?=?NULL)???????{?num?=?n;?next?=?p;}??};????//自定义链表实现??int?JosephusProblem_Solution1(int?n,?int?m)??{??????if(n??1?||?m??1)??????????return?-1;??????ListNode?*pHead?=?new?ListNode();?//头结点??????ListNode?*pCurrentNode?=?pHead;???//当前结点??????ListNode?*pLastNode?=?NULL;???????//前一个结点??????unsigned?i;????????//构造环链表??????for(i?=?1;?i??n;?i++)??????{??????????pCurrentNode-next?=?new?ListNode(i);??????????pCurrentNode?=?pCurrentNode-next;??????}??????pCurrentNode-next?=?pHead;????????//循环遍历??????pLastNode?=?pCurrentNode;??????pCurrentNode?=?pHead;????????while(pCurrentNode-next?!=?pCurrentNode)??????{??????????//前进m?-?1步??????????for(i?=?0;?i??m-1;?i++)??????????{??????????????pLastNode?=?pCurrentNode;??????????????pCurrentNode?=?pCurrentNode-next;??????????}??????????//删除报到m?-?1的数??????????pLastNode-next?=?pCurrentNode-next;??????????delete?pCurrentNode;??????????pCurrentNode?=?pLastNode-next;??????}??????/