约瑟夫环问题单循环链表解法讲解

C语⾔⽤循环单链表实现约瑟夫环⽤循环单链表实现约瑟夫环（c语⾔），供⼤家参考，具体内容如下源代码如下，采⽤Dev编译通过，成功运⾏，默认数到三出局。

主函数：main.c⽂件#include <stdio.h>#include "head.h"#include "1.h"int main(){Linklist L;int n;printf("请输⼊约瑟夫环中的⼈数：");scanf("%d",&n);Createlist(L,n);printf("创建的约瑟夫环为：\n");Listtrave(L,n);printf("依次出局的结果为：\n");Solution(L,n);return 0;}head.h⽂件：#include "1.h"#include <stdio.h>#include <stdlib.h>typedef int Elemtype;typedef struct LNode{Elemtype data;struct LNode *next;}LNode,*Linklist;void Createlist(Linklist &L,int n){Linklist p,tail;L = (Linklist)malloc(sizeof(LNode));L->next = L;//先使其循环p = L;p->data = 1;//创建⾸节点之后就先给⾸节点赋值，使得后⾯节点赋值的操作能够循环tail = L;for(int i = 2;i <= n;i++){p = (Linklist)malloc(sizeof(LNode));p->data = i;p->next = L;tail->next = p;tail = p;}printf("已⽣成⼀个长度为%d的约瑟夫环！\n",n);}void Listtrave(Linklist L,int n)//遍历函数{Linklist p;p = L;for(int i = 1;i <= n;i++){printf("%3d",p->data);p = p->next;}printf("\n");}int Solution(Linklist L,int n){Linklist p,s;p = L,s = L;int count = 1;while(L){if(count != 3){count++;p = p->next;//进⾏不等于3时的移位}else{Linklist q;q = p;//⽤q保存p所指的位置，⽅便进⾏节点的删除if(s->next->data == s->data)//当只有⼀个元素的时候{printf("%3d\n",s->data);free(s);return OK;}else//当有两个及两个以上的元素的时候{count = 1;//先将count重置为1printf("%3d",p->data);//再打印出出局的值while(s->next != p){s = s->next;//将s移位到p的前驱节点处}p = p->next;//使p指向⾃⼰的下⼀个节点s->next = p;//进⾏删除free(q);}}}}1.h⽂件：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2运⾏结果：以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

1．需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；输入的值为数字(2) 输出的形式；输出的形式为一串数字如：6，1，4，7，2，3，5(3) 程序所能达到的功能；编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

输入错误时一般不会显示结果。

总体归纳为：1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。

3.程序执行的命令包括：1）输入初始密码和人数 2）输入所有人的密码 3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号 5）结束4.测试数据(1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4(2)m=7,n=20,20个人的密码依次为3，1，7，2，4，8，4(2)组数据为错误数据测程序的健壮性。

2．概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

ADT LinearList{数据元素：D={ai| ai∈D0, i=1,2,…，n n≥0 ，D0为某一数据对象}关系：Ｓ＝｛<ai,ai+1> | ai, ai+1∈D0，i=1,2, …,n-1｝该程序只有主程序。

pNew->next = pCur->next;
pCur->next = pNew;
pCur = pNew;
printf("结点%d,密码%d\n",pCur->id, pCur->cipher);
}
}
printf("完成单向循环链表的创建!\n");
}
(3)运行"约瑟夫环"问题
static void StartJoseph(NodeType **, int)
exit(-1);
}
pNew->id = iId;
pNew->cipher = iCipher;
pNew->next = NULL;
return pNew;
}
(6)测试链表是否为空,空为TRUE，非空为FALSE
static unsigned EmptyList(const NodeType *pHead)
实验内容
利用循环链表实现约瑟夫环求解。
实验说明
1.问题描述
约瑟夫问题的：编号为1，2，....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
{
if(!pHead)
{
return TRUE;
}
return FALSE;
}
实验中遇到的问题及解决方法
实验结果如下：
实验总结（结果和心得体会）

约瑟夫环问题问题描述：有n个⼈，编号分别从0到n-1排列，这n个⼈围成⼀圈，现在从编号为0的⼈开始报数，当报到数字m的⼈，离开圈⼦，然后接着下⼀个⼈从0开始报数，依次类推，问最后只剩下⼀个⼈时，编号是多少？分析：这就是著名的约瑟夫环问题，关于来历不再说明，这⾥直接分析解法。

解法⼀：蛮⼒法。

我曾将在⼤⼀学c语⾔的时候，⽤蛮⼒法实现过，就是采⽤标记变量的⽅法即可。

解法⼀：循环链表法。

从问题的本质⼊⼿，既然是围成⼀个圈，并且要删除节点，显然符合循环链表的数据结构，因此可以采⽤循环链表实现。

解法三：递推法。

这是⼀种创新的解法，采⽤数学建模的⽅法去做。

具体如下：⾸先定义⼀个关于n和m的⽅程f(n,m)，表⽰每次在n个编号0，1，...，n-1中每次删除的报数为m后剩下的数字，在这n个数字中，第⼀个被删除的数字是(m-1)%n，为了简单，把(m-1)%n记作k，那么删除k之后剩下的数字为0，1，2，...，k-1，k+1，...，n-1并且下⼀次删除的数字从k+1开始计数，这就相当于剩下的序列中k+1排在最前⾯，进⽽形成k+1,..,n-1,0,1,2,...,k-1这样的序列，这个序列最后剩下的数字应该和原序列相同，由于我们改变了次序，不能简单的记作f(n-1,m),我们可以记作g(n-1,m),那么就会有f(n,m)=g(n-1,m).下⼀步，我们把这n-2个数字的序列k+1,..,n-1,0,1,2,...,k-1做⼀个映射，映射的结果是形成⼀个从0到n-2的序列。

k+1对0，k+2对1，......，n-1对n-k-2，0对n-k-1，1对n-k，....，k-1对n-2这样我们可以把这个映射定义为p,则p(x)=(x-k-1)%n,它表⽰如果映射前的数字是x，映射后为(x-k-1)%n,从⽽这个映射的反映射问为p-1(x)=(x+k+1)%n由于映射之后的序列和原始序列具有相同的形式，都是从0开始的序列，所以可以⽤函数f来表⽰，即为f(n-1,m)，根据映射规则有：g(n-1,m)=p-1[f(n-n,m)]=[f(n-1,m)+k+1]%n,最后把之前的k=(m-1)%n带⼊式⼦就会有f(n,m)=g(n-1,m)=[f(n-1,m)+m]%n.这样我们就可以得出⼀个递推公式，当n=1时，f(n,m)=0;当n>1时，f(n,m)=[f(n-1,m)+m]%n;有了这个公式，问题就变得多了。

约瑟夫环知识点总结1. 约瑟夫环的数学模型约瑟夫环可以用数学的方式进行建模和解决。

通常情况下，我们把约瑟夫环的问题理解为一个数学公式的求解。

假设n个士兵分别编号为1、2、3、...、n，m为出列的间隔数。

首先，我们可以得到第一个出列的士兵编号为(m-1)%n+1，例如当n=7，m=3时，第一个出列的士兵为(3-1)%7+1=3。

之后，每次出列后的编号变换规律为：下一个出列士兵的编号为前一个出列士兵编号加上m在n取模后的结果，并且再对n取模，即f(i)=f(i-1)+m)%n。

以上公式是解决约瑟夫环问题的核心，因为根据这个公式可以有效地计算出每一轮出列的士兵的编号。

然后我们只需要循环迭代这个公式，直到最后只有一个士兵为止，这个士兵的编号就是最后的结果。

2. 约瑟夫环的递归解法除了上述的数学模型，还可以使用递归的方法来解决约瑟夫环的问题。

递归是一种非常高效的解决问题的方法，适用于很多数学问题，包括约瑟夫环的计算。

递归方法的求解思路是：先假设已知了n-1个士兵的约瑟夫环问题的解f(n-1, m)，那么我们要求的n个士兵的约瑟夫环的解f(n, m)可以通过以下方式推导得到。

首先，第一个出列的士兵编号为(m-1)%n+1，之后剩下的n-1个士兵重新排列成一个圆圈，编号重新从1到n-1。

将这n-1个士兵的解f(n-1, m)映射到n个士兵的解f(n, m)上，此时，再回到上述的数学模型进行计算，找到最终的结果。

递归的思路虽然清晰，但是在实际求解的过程中，由于递归的不断嵌套，计算量会非常庞大，不适合解决大规模的约瑟夫环问题。

3. 约瑟夫环的迭代解法在解决实际问题的时候，我们更多地使用迭代的方法来求解约瑟夫环的问题。

迭代的思路是从最简单的情况开始，然后不断迭代得到更加复杂的情况的解。

对于约瑟夫环问题，迭代的思路是逐步得出每一轮出列的士兵的编号并记录下来，直到剩下最后一个士兵为止。

通常情况下，我们会使用一个数组或者链表来保存每一轮出列的士兵的编号，最后得出最后一个士兵的编号。

C语言的循环链表和约瑟夫环C语言的循环链表和约瑟夫环约瑟夫问题）是一个数学的应用问题，对于学习C语言四非常挺有帮助的，下面是店铺为大家搜集整理出来的有关于C语言的循环链表和约瑟夫环，一起了解下吧!循环链表的实现单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。

当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：1. 初始化2. 插入3. 删除4. 定位寻找代码实现：1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1void ListInit(Node *pNode){int item;Node *temp,*target;cout<<"输入0完成初始化"<<endl; cin="">>item;if(!item)return ;if(!(pNode)){ //当空表的时候，head==NULLpNode = new Node ;if(!(pNode))exit(0);//未成功申请pNode->data = item;pNode->next = pNode;}else{//for(target = pNode;target->next!=pNode;target = target->next);4 15 16 17 18 19 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 3 0 3 1 3 2 3 3 3 4 3 5 3temp = new Node;if(!(temp))exit(0);temp->data = item;temp->next = pNode;target->next = temp;}}}void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置Node *temp;Node *target;int item;cout<<"输入您要插入的值:"<<endl; cin="">>item;if(i==1){temp = new Node;if(!temp)exit(0);temp->data = item;for(target=pNode;target->next != pNode;target = target->next);temp->next = pNode;target->next = temp;pNode = temp;}else{target = pNode;for (int j=1;j<i-1;++j) target="target-">next;temp = new Node;if(!temp)exit(0);temp->data = item;temp->next = target->next;target->next = temp;}}void ListDelete(Node *pNode,int i){Node *target,*temp;if(i==1){for(target=pNode;target->next!=pNode;target=target ->next);temp = pNode;//保存一下要删除的首节点 ,一会便于释放6 37 38 39 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5pNode = pNode->next;target->next = pNode;temp;}else{target = pNode;for(int j=1;j<i-1;++j) target="target-">next;temp = target->next;//要释放的nodetarget->next = target->next->next;temp;}}int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置Node *target;int i=1;for(target = pNode;target->data!=elem && target->next!= pNode;++i)target = target->next;if(target->next == pNode && target->data!=elem)return 0;else return i;}</i-1;++j)></i-1;++j)></endl;></endl;>5 96 0 6 1 6 2 6 3 6 4 6 5 6 6 67 68 69 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 8约瑟夫问题约瑟夫环(约瑟夫问题)是一个数学的'应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。

约瑟夫环问题的简单解法（数学公式法）关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：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-2 – n-2k-1 – n-1解x’ —- 解为x注意x’就是最终的解变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况—- 这显然就是一个倒推问题！下面举例说明：假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 m=2。

那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换：现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。

福州大学数计学院
《数据结构》上机实验报告
专业和班级：信息计算科学与应用数学6班
学号
姓名
成绩
实验名称
线性表结构及其应用
实验内容
约瑟夫环问题
实
验
目
的
和
要
求
【实验目的】
利用单向循环链表解决约瑟夫环问题，提高综合设计能力。
【基本要求】
利用单向循环链表存储结构模拟此过程,按归口炪列的顺序印出各人的编号.
问
题
描
i=1；
while（i<=n)
｛
printf（”请输入第％d个人的密码：”，i);
scanf（"％d",&pwd)；
if(pwd〈= 0)continue；
Insert(L，pwd, i）；
i++;
｝
i = 1；
p = L-〉next；
while（L->next！= L）
｛
q = p;
p = p->next;
【结果截图】
研
究
与
探
讨
解决约瑟夫环问题有三个算法：
一个是在顺序表上实现，另一个是在单向循环链表上实现，第三个则是利用循环队列的方式来实现。
说明：实验名称为教学大纲中各章的实验项目名称,实验内容为具体章节的实验内容名称
述
和
主
要
步
骤
【问题描述】
约瑟夫问题：编号为1，2，。。n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列,将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止.试设计一个程序求出出列顺序.

约瑟夫环问题的两种解法（详解）约瑟夫环问题的两种解法（详解）题⽬：Josephus有过的故事：39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被敌⼈抓。

于是决定了⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀。

然后下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。

然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。

对于这个题⽬⼤概两种解法：⼀、使⽤循环链表模拟全过程⼆、公式法我们假设这41个⼈编号是从0开始，从1开始报数，第3个⼈⾃杀。

1、最开始我们有这么多⼈：[ 0 1 2 3 4 5 ... 37 38 39 40 ]2、第⼀次⾃杀，则是(3-1)%41=2 这个⼈⾃杀，则剩下：[ 0 1 3 4 5 ... 37 38 39 40 ]3、然后就是从编号为3%41=3的⼈开始从1报数，那么3号就相当于头，既然是头为什么不把它置为0，这样从它开始就⼜是与第1,2步⼀样的步骤了，只是⼈数少了⼀个，这样不就是递归了就可以得到递归公式。

想法有了就开始做：4、把第2步中剩下的⼈编号减去3映射为：[ -3 -2 0 1 2 ... 34 35 36 37 ]5、出现负数了，这样不利于我们计算，既然是环形，37后⾯报数的应该是-3，-2，那么把他们加上⼀个总数（相当于加上360度，得到的还是它）[ 38 39 0 1 2 3 ... 34 35 36 37 ]6、这样就是⼀个总数为40个⼈，报数到3杀⼀个⼈的游戏。

这次⾃杀的是第5步中的(3-1)%40=2号，但是我们想要的是第2步中的编号（也就是最初的编号）那最初的是多少？对应回去是5；这个5是如何得到的呢？是（2+3)%41得到的。

⼤家可以把第5步中所有元素对应到第2步都是正确的。

7、接下来是[ 35 36 37 38 0 1 2... 31 32 33 34 ]⾃杀的是(3-1)%39=2，先对应到第5步中是(2+3)%40=5，对应到第2步是(5+3)%41=8。

循环队列之约瑟夫环问题约瑟夫问题 约瑟夫环（约瑟夫问题）是⼀个数学的应⽤问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。

通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

循环队列求解（链式）#include<stdio.h>#include<stdlib.h>//循环队列//typedef int ElemType;typedef struct QueueNode{int data;struct QueueNode *next;}QueueNode;typedef struct Queue{QueueNode *front;QueueNode *rear;}Queue;void InitQueue(Queue *q){q->front=q->rear=NULL;}void EnQueue(Queue *q , int value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode));temp->data=value;if(q->rear==NULL){temp->next=temp;q->rear=q->front=temp;}else{temp->next=q->rear->next;q->rear->next=temp;q->rear=temp;}}//enter a element from the tailvoid DeQueue(Queue *q, int *value){QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode)); if(q->rear==NULL){return;}// It's nullelse if(q->rear->next==q->rear){*value=q->front->data;free(q->rear);q->rear=q->front=NULL;}//It just has one nodeelse{*value=q->front->data;temp=q->front;q->front=temp->next;q->rear->next=q->front;}//more one nodefree(temp);}//delete a element from the headint main(){Queue *q=(Queue*)malloc(sizeof(Queue));int i,m,n,count,temp;printf("请输⼊⼈数n和循环要报的数m（两数之间留个空格）\n"); scanf("%d%d",&n,&m);for(i=1;i<=n;i++)EnQueue(q,i);printf("出圈序列：\n");while(q->front){ count=1;while(count<m){q->front=q->front->next;q->rear=q->rear->next;count++;}count=1;DeQueue(q,&temp);printf("%d ",temp);}putchar('\n');}简单解法#include <stdio.h>int josephus(int n, int m) {if(n == 1) {return0;}else {return (josephus(n-1, m) + m) % n;}}int main() {int n, m;while (scanf("%d", &n) == 1) {if (!n) {break;}scanf("%d", &m);int result = josephus(n, m);printf("%d\n", result+1);}return0;}。

约瑟夫环问题的三种解法约瑟夫问题是个著名的问题：N个⼈围成⼀圈，第⼀个⼈从1开始报数，报到k的⼈将被杀掉，接着下⼀个⼈⼜从1开始报，直到最后剩下⼀个，求最后留下的⼈的下标。

题⽬集合解法1：暴⼒可以直接暴⼒求解，时间复杂度为O(nk)解法2：递推设f(n,k)为当n个⼈围成⼀圈时，最后留下的⼈的下标。

对于f(n-1,k)来说，其结果相当于f(n,k)的结果向前移动k\%(n-1)位。

因为对于f(n,k)来说，去掉第⼀轮报的数(k\%n)后，现在就只剩下n-1个数，并且是以(k\%(n-1)+1)作为第⼀个数,即所有数向前移动k\%(n-1)位。

现在的结果就为f(n-1,k)对于f(5,3)来说,其结果为4。

当其去掉第⼀轮报的数后，其向前移动了(3\%4)位，以4为起始，f(4,3)结果为1，对应着f(5,3)的结果4向前移动了3位所以反过来看即为,即为f(n-1,k)的结果向后移动k\%(n-1)位即f(n+1,k)=(f(n,k)+k\%n)\%n (x下标从0开始,因为取模结果为[0,n-1])时间复杂度为O(n)ll josephus2(ll n,ll k){ll pos=0;for(int len=1;len<=n;len++){pos = (pos+k)%len;}return pos+1;}递推代码解法3：如果当前这⼀位⼈没被杀掉，则他可以放在幸存者的末尾，直到幸存者数量为1所以对于下标为i的⼈，如果在他前⾯已经被杀掉了q个⼈，那么他的新的下标为n+q(k-1)+x,(1\leq x <k)如下图所⽰，最后被淘汰的编号⼀定是n*k，所以幸存者最后的编号是n*k我们现在需要从幸存者最后的编号中恢复出最初编号假设幸存者这⼀次的编号为p os_{i}，在他后⾯包括他还有x位幸存者，则[pos_{i-1},pos_{i})间⼀定有x个不能被k整除的数这样才能使在他后⾯包括他还有x位幸存者。

约瑟夫环问题知识点总结约瑟夫环问题的描述如下：有n个人（编号从1到n），他们围成一个环形。

从第一个人开始报数，数到m的人被杀掉，然后从被杀掉的人的下一个人开始重新报数，直到所有人都被杀掉为止。

问题的解是最后剩下的那个人的编号。

约瑟夫环问题在计算机科学和数学领域都有着广泛的应用，因为它涉及到循环队列、递归、数学归纳法等多个概念。

以下是约瑟夫环问题的一些重要知识点总结：1. 约瑟夫环问题的递归解法递归是解决约瑟夫环问题的一种常见的方法。

基本思路是将问题分解为规模更小的子问题，并通过解决子问题来解决原始问题。

对于约瑟夫环问题来说，递归的解法是通过递归地计算每轮的幸存者，直到只剩下一个人为止。

递归解法的关键是找到问题的递归关系。

具体而言，对于约瑟夫环问题，如果用f(n, m)表示n个人中最后幸存者的编号，那么可以得出如下的递归关系：f(n, m) = (f(n-1, m) + m) % n其中，%表示取模运算。

该递归关系表明，当有n个人的时候，最后幸存者的编号可以通过n-1个人的最后幸存者的编号计算得到。

2. 约瑟夫环问题的迭代解法除了递归解法之外，约瑟夫环问题还可以通过迭代的方式进行求解。

迭代解法的基本思路是模拟报数和杀人的过程，直到最后只剩下一个人为止。

迭代解法的关键是找到每一轮报数的规律。

具体而言，对于约瑟夫环问题，可以用一个循环队列来模拟报数的过程，每次报数到第m个人就将其从队列中移除。

通过不断循环这个过程，最终可以得到最后幸存者的编号。

3. 约瑟夫环问题的数学解法约瑟夫环问题还可以通过数学的方法进行求解。

具体而言，可以利用数学归纳法来推导出约瑟夫环问题的解析表达式。

这种方法的优点是可以更快地得到结果，但是需要一定的数学推导能力。

通过数学推导，可以得到约瑟夫环问题的解析表达式：f(n, m) = (f(n-1, m) + m) % n其中，f(1, m) = 0。

该表达式可以直接求解出最后幸存者的编号。

有关经典约瑟夫问题的四种解法 约瑟夫问题是信息学奥赛中的⼀类经典且重要的题型，在平常的测试中屡屡出现。

通常题设可抽象为：⼀开始有n个⼈围成⼀个圈，从 1开始顺时针报数，报出m的⼈被踢出游戏.。

然后下⼀个⼈再从1开始报数，直到只剩下⼀个⼈。

　或者：曾经有个⼈在他⾝边，然⽽现在只剩他⼀个⼈。

Who are you? Who am I? Why am I here?⾛的越来越慢，⼈越来越少，可终于还是只剩⼀个了呢。

他们围成⼀圈，随机了⼀个⼈作为1号，然后逆时针依次编号。

1号开始报数，报到 1，他⾛了；然后2号开始报数，2号报了1，3 号报了2 ，于是3 号也⾛了……每⼀轮都从上⼀次出局的下⼀个⼈开始报数，第i轮从1 报到i，报i的⼈出局。

直到只剩他⼀个⼈。

却早已不记得他⾃⼰是谁。

针对不同的数据范围，可以存在如下⼏种做法：1. O(nm) O(nm)的复杂度适⽤于n,m都在30000以内的情况，此类题型较少，例如“约瑟夫游戏”⼀题，n,m<=30000，由于随着游戏的不断进⾏，需要枚举的⼈数越少，所以复杂度实际低于O(nm)。

算法思路：暴⼒模拟即可。

#include<bits/stdc++.h>using namespace std;int T,N,M; bool v[1000100];void wk(){memset(v,0,sizeof(v));scanf("%d%d",&N,&M);int t=0,num=0,pos=1;while(1){if(v[pos]){++pos;if(pos==N+1) pos=1;continue;}++num;if(num==M){if(t==N-1){printf("%d\n",pos);return;}v[pos]=1,++t,num=0;}++pos;if(pos==N+1) pos=1;}}int main(){scanf("%d",&T);while(T--) wk();return 0;}暴⼒模拟约瑟夫问题2.O(n) O(n)算法已经适⽤于⼤多数约瑟夫问题，让n<=1e7的数据范围可以被轻松解决，考虑以任意⼀⼈为起点，选出第m个⼈后的编号变化，设起始id==0，选出第m个⼈后，id−>(id+m)，再回归到原来的圆形，设i表⽰第i轮游戏，那么整体的公式即为(id+m)%(n−i+1)。

约瑟夫环问题详解很久以前，有个叫Josephus的⽼头脑袋被门挤了，提出了这样⼀个奇葩的问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列这就是著名的约瑟夫环问题，这个问题曾经风靡⼀时，今天我们就来探讨⼀下这个问题。

这个算法并不难，都是纯模拟就能实现的。

思路⼀：⽤两个数组，mark[10000]和num[10000],mark这个数组⽤来标记是否出队，num这个⽤来存值，然后每次到循环节点的时候就判断mark是否为0(未出队)，为0则输出num[i]，并标记mark[i]=1，直到所有的num都出队。

附上C++代码：#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<cctype>#include<cmath>#include<algorithm>using namespace std;char num[1000];bool mark[1000];int main(){while(true){memset(mark,0,sizeof(mark));int n;int k,m;int i,j;int del=k-1;cin>>n>>k>>m;for(i=0;i<n;++i){cin>>num[i];}int cnt=n;for(i=cnt;i>1;--i){for(int j=1;j<=m;){del=(del+1)%n;if(mark[del]==0)j++;}cout<<num[del]<<" ";mark[del]=1;}for(i=0;i<n;++i){if(mark[i]==0)break;}cout<<endl<<"The final winner is:"<<num[i]<<endl;}return 0;}思路⼆：⽤⼀个数组就可，每次到了循环节点了就将num[i]输出，然后将后⾯的值往前移动⼀位，直到所有的节点出列。

约瑟夫问题(数学解法及数组模拟)约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。

在计算机编程的算法中，类似问题又称为约瑟夫环。

又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从。

首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。

接着，再越过k-1个人，并杀掉第k个人。

这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

? 以上来自百度百科约瑟夫问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者，其余人都将被杀掉。

例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

约瑟夫问题其实并不难，但求解的方法多种多样；题目的变化形式也很多。

接下来我们来对约瑟夫问题进行讨论。

1.模拟解法优点 : 思维简单。

?缺点：时间复杂度高达O(m*n)当n和m的值较大时，无法短时间内得到答案。

为了叙述的方便我们将n个人编号为：1- n ，用一个数组vis 来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态int t = 0; --模拟位置int s = 0; --死亡人数int cnt = 0; --计数器if(t n) t = 1;if(!vis[t]) cnt++; --如果这里有人,计数器+1if(cnt == m) --如果此时已经等于m,这这个人死去cnt = 0; --计数器清零s++; --死亡人数+1vis[t] = 1 --标记这个位置的人已经死去coutt" "; --输出这个位置的编号}while(s != n);接下来我们来看另一种更为高效快速的解法数学解法我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最初的编号是多少？我们只需要将最后求得的解加1就能得到原来的编号。

约瑟夫环问题（最简单的数学解法）基本问题描述：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为1的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列。

（也类似于变态杀⼈狂问题）通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

通常，我们会要求输出最后⼀位出列的⼈的序号。

那么这⾥主要研究的是最后⼀个出列的⼈的序号要怎么确定。

当n，m数据量很⼩的时候，我们可以⽤循环链表模拟约瑟夫环的过程。

当模拟到⼈数等于1的时候，输出剩下的⼈的序号即可。

这种⽅法往往实现起来⽐较简单，⽽且也很容易理解。

但是时间复杂度却是很糟糕的，达到了O（n m），这样的话，其实在n，m⽐较⼤的时候（n m达到10^8或者更⼤），那么要得出结果往往需要耗费很长的时间，但是我们可以运⽤⼀点数学上的技巧，将最后结果推导出来。

为了简化出列的过程：⾸先我们把这n个⼈的序号编号从0~n-1（理由很简单，由于m是可能⼤于n的，⽽当m⼤于等于n时，那么第⼀个出列的⼈编号是m%n，⽽m%n是可能等于0的，这样编号的话能够简化后续出列的过程），当数到m-1的那个⼈出列，因此我们编号完成之后，开始分析出列的过程：第⼀次出列：⼀开始的时候，所有⼈的编号排成序列的模式即为：0,1,2,3,4,5...n-2，n-1那么第⼀次出列的⼈的编号则是(m-1)%n1，那么在第⼀个⼈出列之后，从他的下⼀个⼈⼜开始从0开始报数，为了⽅便我们设k1 =m%n1（n1为当前序列的总⼈数）那么在第⼀个⼈出列之后，k1则是下⼀次新的编号序列的⾸位元素，那么我们得到的新的编号序列为：k1，k1+1，k1+2，k1+3...n-2，n-1，0，1，2...k1-3，k1-2 (k1-1第⼀次已出列)那么在这个新的序列中，第⼀个⼈依旧是从0开始报数，那么在这个新的序列中，每个⼈报的相应数字为：0,1，2,3....n-2那么第⼆次每个⼈报的相应数字与第⼀次时⾃⼰相应的编号对应起来的关系则为：0 --> k11 --> k1+12 --> k1+2...n-2 ---> (k1+n-2)%n1(n1为当前序列的总⼈数，因为是循环的序列，k1+n-1可能⼤于总⼈数)那么这时我们要解决的问题就是n-1个⼈的报数问题（即n-1阶约瑟夫环的问题）可能以上过程你还是觉得不太清晰，那么我们重复以上过程，继续推导剩余的n-1个⼈的约瑟夫环的问题：那么在这剩下的n-1个⼈中，我们也可以为了⽅便，将这n-1个⼈编号为：0,1,2,3,4...n-2那么此时出列的⼈的编号则是（m-1） % n2（n2为当前序列的总⼈数），同样的我们设k2 = m % n2，那么在这个⼈出列了以后，序列重排，重排后新的编号序列为：k2，k2+1，k2+2，k2+3...n-2，n-1，0，1，2...k2-3，k2-2 (k2-1第⼀次已出列)那么在这个新的序列中，第⼀个⼈依旧是从1开始报数，那么在这个新的序列中，每个⼈报的相应数字为：1,2，3,4....n-2那么这样的话是不是⼜把问题转化成了n-2阶约瑟夫环的问题呢？后⾯的过程与前两次的过程⼀模⼀样，那么递归处理下去，直到最后只剩下⼀个⼈的时候，便可以直接得出结果当我们得到⼀个⼈的时候（即⼀阶约瑟夫环问题）的结果，那么我们是否能通过⼀阶约瑟夫环问题的结果，推导出⼆阶约瑟夫环的结果呢？借助上⾯的分析过程，我们知道，当在解决n阶约瑟夫环问题时，序号为k1的⼈出列后，剩下的n-1个⼈⼜重新组成了⼀个n-1阶的约瑟夫环，那么假如得到了这个n-1阶约瑟夫环问题的结果为ans（即最后⼀个出列的⼈编号为ans），那么我们通过上述分析过程，可以知道，n阶约瑟夫环的结果(ans + k)%n(n为当前序列的总⼈数)，⽽k = m%n则有：n阶约瑟夫环的结果(ans + m % n)%n，那么我们还可以将该式进⾏⼀下简单的化简：当m<n时，易得上式可化简为：（ans + m）% n⽽当m>=n时，那么上式则化简为：（ans % n + m%n%n）% n即为：（ans % n + m%n）% n⽽（ans + m）% n = （ans % n + m%n）% n因此得证(ans + m % n)%n = （ans + m）% n这样的话，我们就得到了递推公式，由于编号是从0开始的，那么我们可以令f[1] = 0； //当⼀个⼈的时候，出队⼈员编号为0f[n] = (f[n-1] + m)%n //m表⽰每次数到该数的⼈出列，n表⽰当前序列的总⼈数⽽我们只需要得到第n次出列的结果即可，那么不需要另外声明数组保存数据，只需要直接⼀个for循环求得n阶约瑟夫环问题的结果即可由于往往现实⽣活中编号是从1-n，那么我们把最后的结果加1即可。

Josephus环问题约瑟夫环问题问题描述：Josephus问题可以描述为如下的⼀个游戏：N个⼈编号从1到N，围坐成⼀个圆圈，从1号开始传递⼀个热⼟⾖，经过M次传递后拿着⼟⾖的⼈离开圈⼦，由坐在离开的⼈的后⾯的⼈拿起热⼟⾖继续进⾏游戏，直到圈⼦只剩下最后⼀个⼈。

例如：M=0，N=5，则游戏⼈依次被清除，5号最后留下；如果M=1，N=5，那么被清除的⼈的顺序是2,4,1,5，最后剩下的是3号。

如下是两种解题⽅法：建⽴⼀个N⼤⼩的数组，存储N个⼈是否还在圈⼦内（0为在圈⼦内，-1为已经离开圈⼦），依次循环遍历整个数组，直到剩下的⼈数（left）为1。

public static void pass(int m, int n){int[] num = new int[n];int left = n; //剩下的⼈数int index = 0; //当前遍历到的位置while(left != 1){for(int i = 0; i< m; i++){if(num[index++] != 0) //如果当前⼈已经清除i--;if(index >= n)index = 0;}while(num[index] != 0){index++;if(index >= n)index = 0;}System.out.println("out number is " + (index + 1));num[index] = -1; //将清除的数据下标置-1index++;if(index >= n)index = 0;left--;}}第⼆种⽅式，将1~N的数添加到⼀个ArrayList对列中，⾸先计算偏移量（mPrime），当mPrime⼩于对列长度的⼀半时，则从前往后依次遍历找到清除的元素；当mPrime⼤于对列长度的⼀半时，从后往前遍历找到清除的元素。

public static void pass2(int m, int n){ArrayList<Integer> list = new ArrayList<Integer>();for(int i = 1; i <= n; i++)list.add(i);ListIterator<Integer> iter = list.listIterator();int left = n; //剩下的⼈数int item = 0; //the out numberfor(int i= 1; i < n; i++){int mPrime = m % left;if(mPrime < left/2){ //如果当前的偏移量⼩于list长度的⼀半时if(iter.hasNext())item = iter.next();for(int j = 0; j < mPrime; j++){if(!iter.hasNext())iter= list.listIterator();item = iter.next();}}else{ //当偏移量⼤于list长度的⼀半时，从后往前找for(int j = 0; j< left - mPrime; j++){if(!iter.hasPrevious())iter = list.listIterator(list.size());item = iter.previous();}}System.out.println("out number is " + item);iter.remove();if(!iter.hasNext()) //有可能下⼀次循环mPrime就会⼩于left的⼀半iter = list.listIterator();left--;}}总结当M，N较⼤时，则第⼆种⽅法时间效率更⾼，实现表明，当N=100000，M=9000时（省略的两个算法中的syso语句），⽅法⼀个执⾏时间是30713ms，⽽第⼆种⽅法的执⾏时间仅为4891ms，M越⼤时⽅法⼀的时间效率会更差。