约瑟夫环_wuzhekai的专栏

你是否正在寻找关于约瑟夫环的内容？让我把最吸引人的东西奉献给你：

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第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(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; } //释放空间 int result = pCurrentNode->num; delete pCurrentNode; return result; }
//使用标准库 int JosephusProblem_Solution2(int n, int m) { if(n < 1 || m < 1) return -1; list

以上就是关于约瑟夫环的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-98-1.html