约瑟夫环问题

小C哈哈哈

114899人浏览 · 2021-01-24 15:28:03

小C哈哈哈 · 2021-01-24 15:28:03 发布

一、问题描述

约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），第一个人的编号为0或者1（两个都可以，看你的程序如何编写），假设这边我将第一个人的编号设置为1号，那么第二个人的编号就为2号，第三个人的编号就为3号，第N个人的编号就为N号，现在提供一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局，请问，这个出局的顺序是什么？

举一个简单的例子：假设现在N的值为10，代表有10个人，M的值为3，代表报数报到3的人出局，那么出局的顺序就为：3 6 9 2 7 1 8 5 10 4

分析：

如上图所示，圈内矩形格子中的数字代表每个人的编号，从1开始编号到10。圈外半椭圆中的数字代表10个人的出局顺序。

注意：已经出局的人无需报数，报数的都是未出局的人。

从第一个人开始报数，报到3的人出局，因此，第一个出局的人为3号，3号出局之后，要从出局的这个人（3号）的下一个未出局的人（4号）重新开始从1开始报数，所以4号从1开始继续报数，那么，第二个出局的人就是6号，6号出局之后，要从出局的这个人（6号）的下一个未出局的人（7号）重新开始从1开始报数，所以7号从1开始继续报数，那么，第三个出局的人就是9号，9号出局之后，要从出局的这个人（9号）的下一个未出局的人（10号）重新开始从1开始报数，所以10号从1开始继续报数，那么第四个出局的人就是2号（10号报1，1号报2，2号报3，2号出局），2号出局之后，要从出局的这个人（2号）的下一个未出局的人（4号，这边3号已经出局了，不能报数，所以直接跳到4号）重新开始从1开始报数，那么第五个出局的人就是7号，7号出局之后，要从出局的这个人（7号）的下一个未出局的人（8号）重新开始从1开始报数，那么第六个出局的人就是1号，1号出局之后，要从出局的这个人的下一个未出局的人（4号）重新开始从1开始报数，那么第七个出局的人就是8号，8号出局之后，要从出局的这个人（8号）的下一个未出局的人（10号）重新开始从1 开始报数，那么第八个出局的人就是5号，5号出局之后，要从出局的这个人（5号）的下一个未出局的人（10号）重新开始从1开始报数，那么第九个出局的就是10号，10号出局之后，要从出局的这个人（10号）的下一个未出局的人（4号）重新开始从1开始报数，此时，N个人从只剩下4号还未出局，4号自己从1开始报数，自己数到3，那么它也出局了，4号是第十个出局的人。

二、 3种解题方式的思路

⭕数组方式（前提要求：学习过数组并且已经掌握其基本使用）

目的：在给定M的情况下求出N个人的出局顺序

所需变量和数据结构：

数组：一开始将所有的元素初始化为0，0代表一开始所有人都处于未出局的状态，一旦某个人出局，将其对应的数组元素的值设为非0的一个数，代表他不再报数

N：代表N个人 😄 M：从1开始，报到M这个数的人出局

cnt：统计已经出局的人 🤭 i：既代表数组的下标，也代表每个人的编号

k：用来计数，从0开始，一旦k的值达到M，代表当前这个人需要出局，并且k的值需要重新置为0，这样才能找到所有需要出局的人

代码：
#include<bits/stdc++.h>
using namespace std;
//用数组实现约瑟夫环问题
int a[110]={0};   //元素值为0表示未出局 
//i既代表数组的下标，也代表每个人的编号
//k是用来计数的，一旦k的值达到m，代表此人需要出局，并且k需要重新计数，这样才能够找出所有需要出局的人
//数组的0代表未出局的人，数组非0代表出局的人，未出局的人需要报数，出局的人不需要报数 
int main()
{
	int N,M;
	int cnt=0,i=0,k=0;  //cnt表示目前出局的人数 
	cin>>N>>M;  //表示总共有n人，数到数字m时出局 
	while(cnt!=N) //因为要求N个人的出局顺序，因此当cnt（用来统计已经出局的人）未达到n时，需要循环不断报数 
	{
		i++;   //i是每个人的编号 
		if(i>N) i=1;  //这里需要特别注意：i的值是不断累加的，一旦发现i的值>N，那么i需要重新从第1个人开始
		              //数组要从第一个元素重新开始一个一个往后判断 
		if(a[i]==0)   //只有元素值为0的人 才需要报数，元素值为非0的代表已经出局了，不用报数 
		{
			k++;
			if(k==M)     //代表已经某个人已经报了M这个数，需要出局 
			{
				a[i]=1;  //编号为i的这个人出局 
				cnt++;   //出局的人数+1 
				cout<<i<<" ";  //输出出局的人的编号 
				k=0;   //清空k，让下一个人重新从1开始报数   
			}
		}
	}
	return 0;
} 
样例测试：

输入：10 3

输出：

拓展：以上的代码中人编号是从1开始的，如果编号从0开始，那么出局的顺序是怎样的呢？代码应该如何修改呢？

第一种方式：如下图所示

输出结果如下：

第二种方式：

输出结果如下；

⭕循环链表方式（前提要求：学习过循环链表并且已经掌握循环链表的基本使用）

目的：在给定M的情况下求出N个人的出局顺序

所需变量和数据结构：

结构体：作为链表结点，包含两个域，分别是data（数据域）和next（指针域，指向下一个结点），数据域存储每个人的编号，我们这边的编号假设还是从1开始

头指针head：用来指向整个链表的第一个结点 😄 p指针：用来指向某个结点（作用等一下再说） 😄 r指针：用来指向某个结点（作用等一下再说）

N：代表N个人 😄 M：从1开始，报到M这个数的人出局

结构体代码：
typedef struct node  //typedef用来重命名struct node这种数据类型，将其命名为Node 
{
	int data;
	struct node* next;
}Node;
初始化链表：
	//初始化循环链表
	Node *head = NULL,*p=NULL,*r=NULL;   //head为头指针，指向链表的第一个结点，一开始赋值为NULL,代表不指向任何结点 
	head = (Node*)malloc(sizeof(Node));  //让head指向一个实际的空间
	if(NULL==head)  //内存空间可能会申请失败,大多数情况不会申请失败 
	{
			cout<<"Memory Failed!";
			return;
	} 
	head->data=1;       //从1开始编号 
	head->next=NULL;    //一开始整个链表只有一个Node(结点)，这个Node有两个域，分别是data和next
	                    //data从1开始，next指向NULL，总共需要N个结点，现在创建了一个，还需要N-1个 
    p=head;             //head要保持不能改变，才能够找到链表的起始位置，一开始p也指向第一个结点
	                    //p等一下会被使用，用它可以便于创建剩下的N-1个结点 
尾插法创建N-1个结点（尾插法指的是每次新建的结点都插入在链表的最末尾）：
	//尾插法创建链表,已经有一个1号结点了，还需要创建剩下的n-1个结点 
	for(int i=2;i<=N;i++)
	{
		r=(Node*)malloc(sizeof(Node)); 
		r->data=i;
		r->next=NULL;
		//插入结点 
		p->next=r;
		p=r;
		
	}
创建循环链表：
	//创建循环链表
	p->next=head;   //最后一个结点的next指向头结点
	p=head;         //为后续方便，将p指向头结点
约瑟夫环的模拟：
	while(p->next!= p)  //如果p的next=p，说明目前只有一个元素 
	{
		for(int i=1;i<M;i++)  //报到数字为M的时候出局 
		{
			  r=p;   //保留出局的前一个结点 
			  p=p->next; //p指向的是要出局的这个结点，需要保留前一个结点
		}
		// 输出
		cout<<p->data<<" ";
		r->next=p->next;    //删除p的目的，此时p指向哪里？  ：  
		p=p->next;  //更新p重新进行报数 
	} 
	cout<<p->data; 
举例说明：

当N=3（总人数），M=2（报到2的人出局）为例，来说明一下代码流程

第一步😄：创建一个头指针head，此时头指针指向NULL，代表未指向任何结点。同时需要创建一个指针p和一个指针r，作用等一下说，一开始也指向NULL
Node *head = NULL,*p=NULL,*r=NULL; 
第二步🤭：创建第一个结点，将head指向第一个结点，因为咱们代码编号从1开始，因此第一个结点的数据域置为1，此时只有一个结点，第一个结点的指针域置为NULL
head = (Node*)malloc(sizeof(Node));
head->data=1;
head->next=NULL;  
第三步💪：为了便于创建剩下的两个结点，将p这个指针一开始先指向第一个结点，也就是p=head
 p=head; 
第四步😊：用尾插法创建剩下的2个结点，一个结点的编号为2，另一个结点的编号为3
	for(int i=2;i<=N;i++)
	{
		r=(Node*)malloc(sizeof(Node)); 
		r->data=i;
		r->next=NULL;
		//插入结点 
		p->next=r;
		p=r;
		
	}
此时N为3，因此for循环中的i从2遍历到3，i刚好代表编号，此时我们可以看到要创建剩下的N-1（2个）个，那么因为1号结点已经创建了，所以i从2开始，到N结束（N号），for循环总共循环N-1次，代码这里 r的作用就是用来指向当前申请的结点，当i为2的时候，创建编号为2的第二个结点，首先申请一个结点，然后将r指向这个结点，把这个结点的数据域，也就是data，赋值为2，也就是当前i的值，然后将这个结点的指针域赋值为NULL，紧接着，千万要注意啦，因为我们使用的是尾插法（新结点插入到尾部），所以此时我们的p就派上用场啦，p一开始指向头结点（1号结点），此时为了将2号结点放在1号结点后面，我们需要执行：p->next=r；这条语句，将2号结点接在1号结点（头结点）后面，紧接着，又要注意啦，我们这个时候，需要将p这个指针指向刚插入进来的这个结点（也就是2号结点），方便下一个结点的插入，也就是执行p=r；这条语句。当p=r;这条语句执行完毕之后，就会进入下一个循环，此时i=3，代表要创建3号这个结点，和前面一样的道理，首先需要申请一个结点，然后将r指向刚申请的这个结点，然后将这个结点的数据域设置为3，也就是当前的i，将指针域设置为NULL，然后还是一样的，执行p->next=r；这条语句，别忘记了，此时因为上一步处理过了，p此时指向的是2号结点，也就是链表的最后一个结点，现在3号结点来了，需要将3号结点接在2号结点后面，因此需要执行这句话，然后继续将r的值赋值给p，也就是p=r，p此时指向3号结点，p指向链表的最后一个结点是为了方便新结点的插入。至此，链表已经创建完毕。

第五步✊：使用链表成为循环链表

因为讨论的是约瑟夫环的问题，我们需要将第四步创建好的链表变成一个循环链表，很简单，只需要执行一句代码即可
p->next=head;   //最后一个结点的next指向头结点
第六步😊：为了方便后续的约瑟夫环的模拟，我们需要将p这个指针指向头结点
p=head;         //为后续方便，将p指向头结点
第七步🤭：约瑟夫环的模拟
//约瑟夫环的模拟
	while(p->next!= p)  //如果p的next=p，说明目前只有一个元素 
	{
		for(int i=1;i<M;i++)  //报到数字为M的时候出局 
		{
			  r=p;   //保留出局的前一个结点 
			  p=p->next; //p指向的是要出局的这个结点，需要保留前一个结点
		}
		// 输出
		cout<<p->data<<" ";
		r->next=p->next;    //删除p的目的，此时p指向哪里？  ：  
		p=p->next;  //更新p重新进行报数 
	} 
	cout<<p->data; 
p一开始指向头结点，也就是指向编号为1的这个结点，仔细观察代码，循环结束的条件：当链表中的结点个数=1个的时候结束，当链表中的结点个数为1个的时候，因为这是一个循环链表，那么此时p->next必然等于p，所以会退出循环，既然只剩下1个了，那么这一个人一定是最后出局的人，直接通过cout<<p->data；这条语句输出出局编号即可。那我们来看一下while循环内部是如何执行的，首先，我们看到内部是一个for循环，for循环用来找出要出局的人，咱们现在的例子M的值为2，因此，循环从1开始，执行1次，此时p指向2号结点，2号结点需要出局，但是，因为是一个链表，为了删除这个2号结点，我们需要记录当前这个待删除结点的前一个结点，也就是1号结点，我们使用r，将1号结点记录下来（在p未更新之前），然后for循环结束之后，执行cout<<p->data；语句，输出2号，然后执行删除操作，将当前要删除结点的前一个结点的指针域指向当前要删除结点的下一个结点，也就是执行语句：r->next=p->next，然后重新更新p的值，p此时要指向要删除结点的下一个结点，因为等一下要从p开始从1开始报数，因为p->next!=p，此时p指向3号结点，3号结点的next为1号结点，所以while循环继续，进入while循环体中，for循环从1开始，M还是2，循环1次，此时p指向1号结点，r指向3号结点，p指向的1号结点出局，然后紧接着删除1号结点，也就是将3号结点的next指针域指向p->next，此时p->next刚好是3号结点自己，然后更新p的值，也就是执行p=p->next语句，此时p指向3号结点，3号结点的next指针域刚好指向自己，所以while循环的判断条件为false（假），循环退出，最终，将3号结点进行输出，所以，最终的输出结果为2，1，3。

完整代码如下：
#include<bits/stdc++.h>
using namespace std;
//用链表实现约瑟夫环问题 （循环链表） 

typedef struct node  //typedef用来重命名struct node这种数据类型，将其命名为Node 
{
	int data;
	struct node* next;
}Node;

void ysflb(int N,int M)  //总共有N个人，报到数字为M的人出局 
{
	//初始化循环链表
	Node *head = NULL,*p=NULL,*r=NULL;   //head为头指针，指向链表的第一个结点，一开始赋值为NULL,代表不指向任何结点 
	head = (Node*)malloc(sizeof(Node));  //让head指向一个实际的空间
	if(NULL==head)  //内存空间可能会申请失败,大多数情况不会申请失败 
	{
			cout<<"Memory Failed!";
			return;
	} 
	head->data=1;       //从1开始编号 
	head->next=NULL;    //一开始整个链表只有一个Node(结点)，这个Node有两个域，分别是data和next
	                    //data从1开始，next指向NULL，总共需要N个结点，现在创建了一个，还需要N-1个 
    p=head;             //head要保持不能改变，才能够找到链表的起始位置，一开始p也指向第一个结点
	                    //p等一下会被使用，用它可以便于创建剩下的N-1个结点 
						 
	//尾插法创建链表,已经有一个1号结点了，还需要创建剩下的n-1个结点 
	for(int i=2;i<=N;i++)
	{
		r=(Node*)malloc(sizeof(Node)); 
		r->data=i;
		r->next=NULL;
		//插入结点 
		p->next=r;
		p=r;
		
	}
	//创建循环链表
	p->next=head;   //最后一个结点的next指向头结点
	p=head;         //为后续方便，将p指向头结点
	
	//约瑟夫环的模拟
	while(p->next!= p)  //如果p的next=p，说明目前只有一个元素 
	{
		for(int i=1;i<M;i++)  //报到数字为M的时候出局 
		{
			  r=p;   //保留出局的前一个结点 
			  p=p->next; //p指向的是要出局的这个结点，需要保留前一个结点
		}
		// 输出
		cout<<p->data<<" ";
		r->next=p->next;    //删除p的目的，此时p指向哪里？  ：  
		p=p->next;  //更新p重新进行报数 
	} 
	cout<<p->data; 
}

int main()
{
	ysflb(10,3);
	return 0;
} 
当N为10，M为3时，程序的输出结果如下：

⭕递归方式（前提要求：学习过递归并且已经掌握递归的基本使用）— 这种方式可以不看，因为它确实较难理解😔不过还是要有信心学习😄

既然是利用递归求解，那么我们首先肯定要明确，递归函数所代表的含义，这里我暂且将递归函数命名为ysf：ysf(int N,int M,int i)：这个递归函数代表的意思为：有N个人，报到数字M时出局，求第i个人出局的编号。

比如：ysf(10,3,1)=2（假设人从0开始编号）代表的意思就是有10个人，报到数字3时出局，第1个出局的编号为2

我们先来推：当i为1时，出局的人编号的数学公式，我们来看一个例子：假设现在总共有10个人，从0开始编号，那么就是0-9，如下图所示

现在，M=3，i=1，那么第一个出局的人就是2号，如下图，到目前为止，我们可以知道当i=1时，出局的人为：M-1

现在我们再来看另外一种情况，还是10个人，不过现在M变为11，i还是1，难道现在第一个出局的人还是M-1吗？11-1=10？，根本就不存在编号为10的这个人，此时应该出局的应该是编号为0的这个人，那怎么办呢？可以这样：(M-1)%N，那么不管M=3还是M=11，都可以正确得出第一个出局的人的编号。

第一个人出局的编号是完全可以通过数学公式计算而来，无需通过递归

接下来就是比较重要的了，我们还是以N=10（总人数），M=3（报的数）这个例子来说明，初始情况为：

当报数报到3，出局一个之后，变为：

此时，这些编号已经不连续了，但是3 4 5 6 7 8 9 0 1 这些数字还是紧挨着的，且下一次报数从3开始，但是，之后的报数总要考虑原编号2处空位问题

如何才能避免已经产生的空位对报数所造成的影响呢？

可以将剩下的9个连在一起的数组成一个新的环（将1、3连接），这样报数的时候就不用在意3的空位了。但是新产生的环的数字并非连续的，这就比较麻烦了。

我们需要想一种办法来解决：我们可以将组成的新的环重新编号，怎么做呢？，我们可以从刚刚出局的人的下一个人开始从0进行编号，如下图所示

但是这个时候问题又来了，怎么做才能使得在新一轮的编号中按照原规则报数得到的结果推出在旧一轮中对应的数字？，我们继续看例子，现在继续在新一轮中开始报数，那么当报数到3的时候，2号出局。此时到底怎么通过2号来推出在旧一轮中应该出局的正确编号？如何由新一轮中的2得到旧一轮中的5呢？

新一轮中的编号：（旧一轮中的编号-最大报数值M）%旧一轮中的总人数

那么，旧一轮中的编号：（新一轮的编号+最大报数值M）%旧一轮中的总人数

接下里非常重要啦！也就是说，原序列（N个人）中第二次出局的编号可以由新序列（N-1个人）第一次出局的编号通过特定的公式运算得出。

新序列（N-1个人）的编号也是从0开始的，还是这个图：

针对于这个新序列（N-1个人）第二次出局的人可以由（N-2个人）的新序列的第一次出局的人通过特定的公式推出，并且(N-1个人)这个序列第二次出局的人的编号与（N个人）这个原序列中第三次出局的人的编号是有对应关系的。

这样讲大家可能还是云里雾里的，不太明白，没有关系，接下来我们举一个例子大家就都能明白啦！，我们先来看两张图，一定要重点理解这两张图

我们以第一图为例子讲解：N=10，M=3

第一步💪：当N个人时，第一个需要出局的人为2号（编号从0开始：0-9），那么剩下的序列就是

第二步💪：第一步出局2号之后，剩下N-1个人，将N-1个重新编号，如下：

此时，从新一轮编号开始重新报数，报到2的时候出局，那么我们可以通过2推算出5，从而得到N个人中第二个出局的人是编号5，怎么推算呢？

旧编号=（新编号+最大报数值M）%旧一轮的人数取余（2+3）%10=5；

第三步💪：接下来又需要新的一轮，即N-2个人

第四步💪：将N-2个人重新进行编号，得到下图

第五步💪：N-2个人又要报数出局，而N-2个人第1个出局的人就是N-1个人时第二个出局的人，此时可以看出2号出局，如何通过2号推算出N-1个人出局时的第二个人的编号?

旧编号=（新编号+最大报数值M）%旧一轮的人数取余（2+3）%9=5；

所以N-1轮的时候第二个出局的人对应的编号是5号，而通过N-1第2个出局的人也就是5号，又可以推算出N个人时出局的第3个人

旧编号=（新编号+最大报数值M）%旧一轮的人数取余（5+3）%10=8；所以N个人时第3个出局的人的编号为8。

往后的步骤以此类推。

递归方法实现的约瑟夫环只有几行，但是理解起来却不简单，希望你们可以多花些功夫钻研，只有这样，才会成长

代码如下：
#include<bits/stdc++.h>
using namespace std;
//用递归实现约瑟夫环问题

int ysfdg(int N,int M,int i)
{
    if(i==1)
    {
    	return (M-1+N)%N;
	}
    return (ysfdg(N-1,M,i-1)+M)%N;
}


int main()
{
	int N,M;
	cin>>N>>M;   //10   3
	for(int i=1;i<=N;i++)
		cout<<ysfdg(N,M,i)<<" ";
	return 0;
} 
输出结果如下图：

三、总结

递归求解约瑟夫环问题确实是比较难，要不断重复去看，去理解，如果不静下心来钻研，很难搞懂，即使搞懂了，没有多去巩固，也很容易忘记。

其实，在代码中，我并不明白标注出来的这个点，但是参考了别人的资料，都是要加上N，我一直在想，如果不加N，会出现什么问题？，希望大家在评论栏里面进行讨论，让我学习一下😄。约瑟夫这个专题就讲到这里啦！我们下期再见ヾ(•ω•`)o!