详解约瑟夫环问题及其相关的C语⾔算法实现约瑟夫环问题N个⼈围成⼀圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的⼈再从1、2、3开始报数，报p的⼈再退出圈外，以此类推。
请按退出顺序输出每个退出⼈的原序号算法思想⽤数学归纳法递推。
⽆论是⽤链表实现还是⽤数组实现都有⼀个共同点：要模拟整个游戏过程，不仅程序写起来⽐较烦，⽽且时间复杂度⾼达O(nm)，若nm⾮常⼤，⽆法在短时间内计算出结果。
我们注意到原问题仅仅是要求出最后的胜利者的序号，⽽不是要读者模拟整个过程。
因此如果要追求效率，就要打破常规，实施⼀点数学策略。
为了讨论⽅便，先把问题稍微改变⼀下，并不影响原意：问题描述：n个⼈（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的⼈继续从0开始报数。
求胜利者的编号。
我们知道第⼀个⼈(编号⼀定是m%n-1) 出列之后，剩下的n-1个⼈组成了⼀个新的约瑟夫环（以编号为k=m%n的⼈开始）:k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做⼀下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2k-1 --> n-1变换后就完完全全成为了(n-1)个⼈报数的⼦问题，假如我们知道这个⼦问题的解：例如x是最终的胜利者，那么根据上⾯这个表把这个x变回去不刚好就是n个⼈情况的解吗变回去的公式很简单，相信⼤家都可以推出来：x'=(x+k)%n如何知道(n-1)个⼈报数的问题的解？对，只要知道(n-2)个⼈的解就⾏了。
(n-2)个⼈的解呢？当然是先求(n-3)的情况——这显然就是⼀个倒推问题！好了，思路出来了，下⾯写递推公式：令f[i]表⽰i个⼈玩游戏报m退出最后胜利者的编号，最后的结果⾃然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)实现⽅法⼀、循环链表建⽴⼀个有N个元素的循环链表，然后从链表头开始遍历并计数，如果基数i == m，则踢出该元素，继续循环，直到当前元素与下⼀个元素相同时退出循环#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct lnode{int pos;struct lnode *next;} lnode;/*** 构建循环链表&&循环遍历*/void create_ring(lnode **root, int loc, int n){lnode *pre, *current, *new;current = *root;pre = NULL;while (current != NULL) {pre = current;current = current->next;}new = (lnode *)malloc(sizeof(lnode));new->pos = loc;new->next = current;if (pre == NULL) {*root = new;} else {pre->next = new;}// 循环链表if (loc == n) {new->next = *root;}}/*** 约瑟夫环*/void kickoff_ring(lnode *head, int p){int i;lnode *pre, *pcur;pre = pcur = head;while (pcur->next != pcur) {for (i = 1; i < p; i ++) {pre = pcur;pcur = pcur->next;}printf("%d ", pcur->pos);pre->next = pcur->next;free(pcur);pcur = pre->next;}printf("%d\n", pcur->pos);free(pcur);}void print_ring(lnode *head){lnode *cur;cur = head;while (cur->next != head) {printf("%d ", cur->pos);cur = cur->next;}printf("%d\n", cur->pos);}int main(){int i, p, n;lnode *head;while (scanf("%d %d", &n, &p) != EOF) { // 构建循环链表for (i = 1, head = NULL; i <= n; i ++) create_ring(&head, i, n);// 约瑟夫环if (p != 1)kickoff_ring(head, p);elseprint_ring(head);}return 0;}/************************************************************** Problem: 1188User: wangzhengyiLanguage: CResult: AcceptedTime:110 msMemory:912 kb****************************************************************/⼆、数组模拟思想跟循环链表类似，少了构建循环链表的过程#include <stdio.h>#include <stdlib.h>int main(){int i, index, p, n, remain, delete[3001], flag[3001] = {0};while (scanf("%d %d", &n, &p) != EOF) {remain = n;index = 0;while (remain >= 1) {for (i = 0; i < n; i ++) {if (flag[i] == 0) {// 报数index ++;// 报p者退出圈外if (index == p) {// 退出圈外flag[i] = 1;// 重新报数index = 0;delete[remain - 1] = i + 1;remain --;}}}}// 输出每个退出⼈的序号for (i = n - 1; i >= 0; i --) {if (i == 0) {printf("%d\n", delete[i]);} else {printf("%d ", delete[i]);}}}return 0;}三、数学推导#include <stdio.h>int main(void){int i, n, m, last;while (scanf("%d", &n) != EOF && n != 0) {// 接收报数scanf("%d", &m);// 约瑟夫环问题for (i = 2, last = 0; i <= n; i ++) { last = (last + m) % i;}printf("%d\n", last + 1);}return 0;}。
