001. 约瑟夫问题(洛谷P1996)

题目描述

\(n\) 个人围成一圈，从第一个人开始报数,数到 \(m\) 的人出列，再由下一个人重新从 \(1\) 开始报数，数到 \(m\) 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 \(n-1\) 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 \(n,m\)。

输出格式

输出一行 \(n\) 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

\(1 \le m, n \le 100\)

题解

解法一：

约瑟夫问题是一个链表的典型题目。为啥要用到链表呢？因为链表的优越性实在太多啦~

首先，有一个叫“循环链表”的东西非常适合这道题

比如样例中n=3，m=10的情况，我们可以建立一个这样的循环链表：

第10个的下一个正好指向第1个，非常符合题目的设定

其次，链表的删除操作非常简便4

如果要删掉数组中的一个元素，需要把它之后的所有元素都向前移一个单位，太麻烦了有木有？！而链表恰恰相反，删除数据的操作很简单，只需要改变他们建立的联系就行

什么意思呢？还是用样例解释：当第3个人出圈之前，他们的关系是这样的：

而出圈之后，他们的关系就成了这样：

也就是说，我们把第2个的下一个直接指向了第4个，从而跳过了第3个

链表好归好，但好多小伙伴肯定会像我一样，一提链表，“指针恐惧症”就犯了 对不对？？？

没关系，我们不用指针，用数组也能搞个链表出来！

链表的关键核心在哪？当然在于某个元素与其它的元素建立的联系，通俗易懂来讲，连表可以轻松地操作某个元素的下一个元素是谁。

那咱们只要把每个元素的下一个元素找出来不就行了？我们可以定义一个数组，来存每个元素的下一个元素。数组名就叫......next好了

因为这个题的数据是1~n连续的，所以我们可以用数组的下标来代表数据的内容。比如next[1]=2就是指第1个人的下一个是第2个，以此类推，next[2]=3,next[3]=4.......第10个（还是用样例）的下一个当然是第1个了。

代码实现是这样的：

int n,m;
    cin>>n>>m;//输入，没啥好说的
    for(int i=0;i<n;i++)//为什么从0开始后边会说
    	next[i]=i+1;//前n-1个的下一个就是第i+1个
    next[n]=1;//最后一个的下一个是第一个，特殊处理

这样数组的初始化就完成了

模拟出圈过程也不难。比如第3个人出圈时，把2的下一个从3改成4，下次到这里的时候从2就会直接到达4，从而跳过3

接下来的任务就是数m个，输出，删掉，再 数m个，输出，删掉......一直重复n次，嵌套循环就能完美解决

首先，咱们定义一个变量p，类似于一个指针。一直重复m次p取下一个的操作。 然后输出出圈人的位置，然后把出圈人的前一个指向他的下下个来跳过出圈人就行了

那么问题来了，如何利用next数组访问下一个呢？

观察咱们列的表表就会发现，我们要访问的数组下标（也就是人的位置）正是next[下标]的值，也就是说

p=next[p];

事已至此，大体的思路就已经搞定了，接下来就是细节的问题。

首先，最好不要让p到达出圈人的位置，因为出圈人的位置是要被跳过的，p留在这里就会很不方便

那咋办呢？？？把p放在出圈人的前一个位置就OK了，输出的话就输出p的下一个，然后把next[p]改成next[p]的下一个，也就是next[next[p]]

除此之外，还要注意一个小小的问题：既然是把p放到出圈人的前一个位置，那就要把p=next[p]执行（m-1）次。但第一次如果从1开始，执行（m-1）次还是到了出圈人的位置，只要把p初始化为0，把next[0]设成1，就万事大吉了，这也是前面代码中next数组的初始化从0开始的原因。

说了这么多，放代码！

int p=0;
//建立p变量（类似指针）来遍历数组，初始化成0
	for(int i=1;i<=n;i++){//n个人出圈n次
		for(int j=1;j<m;j++){
//移动（m-1）次，到达出圈人人的前一个位置
			p=next[p];//p到达下一个
		}
//此时p到达出圈人的前一个位置
		cout<<p[next]<<" "//输出出圈人的位置;
		next[p]=next[next[p]];
//把p指向p的下下个，跳过（删掉出圈人）
	}

万事俱备，只欠AC，这就是用数组模拟链表，你学会了吗？

#include<iostream>
using namespace std;
int next[1000005];
int main(){
    int n,m;
    cin>>n>>m;//输入n、m
    for(int i=0;i<n;i++)//初始化
    	next[i]=i+1;
	next[n]=1;
	int p=0;
	for(int i=1;i<=n;i++){//开始模拟出圈过程
		for(int j=1;j<m;j++)
			p=next[p];//p位置右移
		cout<<p[next]<<" ";//输出出圈人的位置
		next[p]=next[next[p]];//删掉出圈人
	}
	return 0;//功德圆满
}

解法二：

首先我们需要模拟一个队列，将所有的元素压进队列

在进行循环（直到队列为空为止） 首先你要知道：

队列只可以在head删除，那么这就要求我们只要这个人经过判断并且不会被剔除，那么就必须把他排在队尾；

若这个人正好被剔除，那先输出他，再踢除。

下面废话不多说，直接上代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> a;
int main()
{
	int b,c,d,e=1,f=0;
	cin>>b>>c;
	for(int i=1;i<=b;i++)
	{
		a.push(i);//模拟队列 
	}
	while(!a.empty())
	{
		if(e==c)//如果这个人正好被踢 
		{
			cout<<a.front()<<" ";//先输出 
			a.pop();//再删除 
			e=1;//再从1开始报数 
		}
		else if(e!=c)//如果不被剔除 
		{
			e++;//报的数+1 
			a.push(a.front());//先把head压进队尾 
			a.pop();//再把head删除 
		}
	}
	return 0;//结束程序（完美） 
}