约瑟夫环

7-9 约瑟夫环

N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。 请按退出顺序输出每个退出人的原序号。

输入格式:

输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。

输出格式:

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例:

在这里给出一组输入。例如：

7 3

输出样例:

3 6 2 7 5 1 4

要输出每次删的人，只能使用这个模拟

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int n,m,t=0,s=0,die=0;
	bool a[3010],vo=true;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	  a[i]=0;
	do
	{
		t++;
		if (t>n)
		  t=1;
		if (a[t]==0)
		  s++;
		if (s==m)
		{
			s=0;
			a[t]=1;
			die++;
			if (vo==true)
			{
			  cout<<t;
			  vo=false;
		    }
		    else
		      cout<<' '<<t;
		}
	}while (die<n);
	return 0;
}

std约瑟夫环递归算法，不能输出每个删的人，因为每次都对状态进行了改变，从少了一个人的情况开始模拟，递归思想：old=f（new），画一下删除前后的对比图，找新的怎么推出老的就行了，因为要return嘛，然后直到最新的状态（本题是n=1时死掉的是他自己，编号0），然后一步步回溯即可return回到n，这中间状态发生了转移，原本性质也就不保持，不是单纯的模拟了，只能这么写，没法模拟每次杀的人了，模拟之前的编号不好想，就从零开始，然后最后加一吧，可以直接mod n的原因是和整除mod完是0正好符合，只有0到n-1个数列表里，而不会有n，当然删除后只有n-2了，数不清的话可以算一下有1/2(n*(n-1))个数嘛就知道编号是几了，坚持，思维。

#include<iostream>
#include<cstdio>
using namespace std;
int dg(int n,int m)
{ 
	if (n==1)
	    return 0;
    return (dg(n-1,m)+m)%n;
}
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<dg(n,m)+1;
	return 0;
}