「算法」约克瑟夫环
声明
本文章纯属整合了一些约克瑟夫环的解法，均为C语言（毕竟还是小白），很多解法都是有出处的（均留了链接），只是暂时发表一篇试试水。如有侵权请留言。
约克瑟夫环的描述
约瑟夫环问题的具体描述是： 设有编号为1,2,3,..,n的n个(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，才从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人都出列。当 任意给定n和m后，设计算法求n个人出圈的次序。
No.1
话不多说，上代码
#include <stdio.h> int main() { int n,m,i,s=0; printf("input N,M = "); scanf("%d%d",&n,&m); for (i = 2; i <= n; i++) { s = (s + m)%i; } printf("\nThe winner is %d\n",s+1); return 0;
此法及其神奇，我想了半天的题，硬生生没出来是个什么玩意儿， 它这么简短就给码了出来，还没反应过来，人家已经win了。(此法偏向于迭代，无穷套娃)
神奇的思路
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到**(m-1)**的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
（Tip:取余要是没看过的可能很难想到，除了大佬，取余是为了让他报数的 时候重新回到第一个人，就类似于循环链表的感觉）
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。 现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-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]
So, 递推公式:
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
实际上也就是f(n-1)与f(n)报数的编号相差了m;给个例子体会一下： 假设n=10,m=3;
（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。
1， 2， 【3】， 4， 5， 6， 7， 8， 9， 10。
（2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。
1， 2， 【3】， 4， 5， 【6】， 7， 8， 9， 10。
6-3=m;
有了这个公式，我们要做的就是从1到n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1由于是逐级递推，不需要保存每个f[i]。
以上来源链接参考:link
递推的理解版
include <stdio.h> int Joseph(int n,int m)/*计算约瑟夫环的递归函数*/ { if(n <= 1 || m <= 1)//设置游戏人数限定值 return -1; if(n == 2)//设置边界值 { if(m % 2 == 0) return 1; else return 2; } else { return (Joseph(n-1,m) + m-1) % n+1;//递归调用 } } int main() { int n,m,x; scanf("%d %d",&n,&m); x=Joseph(n,m); printf("最后一个数为：%d\n",x); return 0; }
No.2
采用链表的方法： Code By Eric Yang 2009 点我进入原链接
代码如下：（输出的为出圈顺序）
7 #include <stdio.h> 8 #include <stdlib.h> 9 10 // 链表节点 11 typedef struct _RingNode 12 { 13 int pos; // 位置 14 struct _RingNode *next; 15 }RingNode, *RingNodePtr; 16 17 // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 18 void CreateRing(RingNodePtr pHead, int count) 19 { 20 RingNodePtr pCurr = NULL, pPrev = NULL; 21 int i = 1; 22 pPrev = pHead; 23 while(count > 0) 24 { 25 pCurr = (RingNodePtr)malloc(sizeof(RingNode)); 26 i++; 27 pCurr->pos = i; 28 pPrev->next = pCurr; 29 pPrev = pCurr; 30 } 31 pCurr->next = pHead; // 构成环状链表 32 } 33 34 void PrintRing(RingNodePtr pHead) 35 { 36 RingNodePtr pCurr; 37 printf("%d", pHead->pos); 38 pCurr = pHead->next; 39 while(pCurr != NULL) 40 { 41 if(pCurr->pos == 1) 42 break; 43 printf("\n%d", pCurr->pos); 44 pCurr = pCurr->next; 45 } 46 } 47 48 void KickFromRing(RingNodePtr pHead, int m) 49 { 50 RingNodePtr pCurr, pPrev; 51 int i = 1; // 计数 52 pCurr = pPrev = pHead; 53 while(pCurr != NULL) 54 { 55 if (i == m) 56 { 57 // 踢出环 58 printf("\n%d", pCurr->pos); // 显示出圈循序 59 pPrev->next = pCurr->next; 60 free(pCurr); 61 pCurr = pPrev->next; 62 i = 1; 63 } 64 pPrev = pCurr; 65 pCurr = pCurr->next; 66 if (pPrev == pCurr) 67 { 68 // 最后一个 69 printf("\n%d", pCurr->pos); // 显示出圈循序 70 free(pCurr); 71 break; 72 } 73 i++; 74 } 75 } 76 77 int main() 78 { 79 int m = 0, n = 0; 80 RingNodePtr pHead = NULL; 81 printf("---------------Josephus Ring---------------\n"); 82 printf("N(person count) = "); 83 scanf("%d", &n); 84 printf("M(out number) = "); 85 scanf("%d", &m); 86 if(n <= 0 || m <= 0) 87 { 88 printf("Input Error\n"); 89 system("pause"); 90 return 0; 91 } 92 // 建立链表 93 pHead = (RingNodePtr)malloc(sizeof(RingNode)); 94 pHead->pos = 1; 95 pHead->next = NULL; 96 CreateRing(pHead, n); 97 #ifdef _DEBUG 98 PrintRing(pHead); 99 #endif 100 101 // 开始出圈 102 printf("\nKick Order: "); 103 KickFromRing(pHead, m); 104 printf("\n"); 105 system("pause"); 106 return 0; 107 }
看完以上两个代码，你肯定晕的差不多了。
来个简单的吧~~~
#include <stdio.h> #include <stdlib.h> typedef struct node { int number; //数据域，存储编号 struct node*next; }Node; Node * createNode(int x) //创建链表结点 { Node*p; p = (Node*)malloc(sizeof(Node)); p->number = x; //将链表结点的数据域赋值为编号 p->next = NULL; return p; } //创建循环链表 Node* createJoseph (int n) { Node *head,*p,*q; int i; for(i=1; i<=n; i++) { p = createNode(i); //创建链表节点，并finish赋值操作 if (i == 1) //若为头结点 head = p; else q->next = p; q = p; } q->next = head; //末尾结点指向头结点，构成循环链表 return head; } void runJoseph (int n,int m) { Node *p,*q; p = createJoseph(n); //创建一个链表环 int i; while(p->next != p) //若链表数目>1 { for(i=1; i<m-1; i++) //begin计数 p = p->next; //第m个人出圈 q = p->next; //q指向出圈的那个人 p->next = q->next; p = p->next; // printf("%d--",q->number); free(q); } printf("winner=%d\n",p->number); } int main (){ int n,m; scanf("%d%d",&n,&m); runJoseph(n,m); return 0; }
接下来，再来理清一下思路吧。（大佬可止步了）
No.3
报到T的人出圈，怎么表示出圈？要么删除对应的标号，其他的标号前移（如果是数组结构，要依次移动元素，效率低；如果是链表，删除结点也比较麻烦）； 要么设定状态标志位（声明一个状态数组status[N]，status[i] ==0时表示未出圈，出圈时将对应第i号人的status置为出圈的次数； 即status[i]=count）
解决了表示出圈的问题，那如何出圈？如果报数T大于总人数N时， 数组越界问题--->(索引 % 链表长度 进行取余操作) 需要取余才能将报号的范围限制在标号为0~N-1中。
流程如下：
while（出圈人数<总人数) { 从start下标依次查找status为0的下标（需要保存start下标） 计数 判断计数是否等于T 若计数等于T 出圈，更新对应下标的status，出圈人数加1 }
核心代码如下：
void joseph() { int T,N; scanf("%d%d",&T,&N); //T为出列周期，N为N个人，即环的元素个数 int status[1000]; memset(status,0,sizeof(status)); int start,end; start = -1; int count = 0; while(count<N) { int i=0; while(1) { start = (start+1) % N; if(status[start] == 0) { i++; } if(i == T) { ++count; status[start]=count; break; } } } for(int k=0;k<N;k++) printf("%d",status[k]); }
说明：本段为CSDN博主「keepupblw」的原创文章 链接：点我
此方法是真的不理解（orz）
有个公众号的挺容易理解---> <五分钟学算法>
复制粘贴 我理解了 --->
#include <stdio.h> #define N 100000 //记录玩游戏最大人数 int flag[N]={0}; //全部初始化 int main (){ int n=0,m=0; scanf("%d%d",&n,&m); //玩游戏的人数n和出圈的数m int i=0; int count = 0; //记录已经出圈的人数 int num = 0; //报数器 for(i=1;i<=n;i++) flag[i] = 1; //所有人入圈，标志位为1即为在圈内 while(count < n-1){ for(i=1; i<=n; i++){ if(1 == flag[i]){ //在未出圈的人中计数 num++; if(num == m){ //此人数到m就出圈 count++; //出圈人数加一 flag[i] = 0; //标志位赋值为0 num = 0; //报数器清0； } if(count == n-1) break; } } } for(i=1; i<=n; i++) if(1 == flag[i]) printf("winner=%d\n",i); return 0; }
No.4
#include<stdio.h> int main() { int m,n,i,j,k=0,a[100]={0}; scanf("%d%d",&n,&m); if(n>=1&&m<=1000000) { for(i=0;i<n;i++) a[i]=i+1; while(n>1) { i=(i+m-1)%n; //待删除的项的下标，+（m-1）是从删除的元素后又从一开始报数， 隔了m-1个，取余是使人数成环 k++; for(j=i+1;j<n;j++) a[j-1]=a[j]; n--; if(i==n) i=0; } } printf("%d\n",a[i]); return 0; }
原文：点这儿
类似的还有：
#include <stdio.h> #include <string.h> #define N 100 int main() { int m, n, i, j, k = 0; scanf("%d",&n); scanf("%d",&m); int a[N] = {0}; for(i = 0; i < n; i++) a[i] = i+1; while (n > 1) { k=(k+m-1)%n; //k是报m的位置，也是下一轮报数的起点。变量只能用k, 因为只有k=0被初始化过 if (k<n-1){ for (j=k+1;j<=n-1;j++) //如果k如果在中间，则要删除A[k] a[j-1]=a[j]; } else k=0; //如果k在末尾，则下一个报数的是0位置 i=k; //因为最后的输出是a[i],所以i就是k n-=1; /********** End **********/ } printf("最后一个出列的是%d", a[i]); return 0;
写在后边：以上文章内容纯属自己的一个归类，源代码均附上了原作者的链接，如有不妥，请留言删除。
