1073 约瑟夫环

http://www.51nod.com/Challenge/Problem.html#!#problemId=1073

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。

 收起

输入

2个数N和K，表示N个人，数到K出列。(2 <= N, K <= 10^6)

输出

最后剩下的人的编号

输入样例

3 2

输出样例

3

 

刚开始我也是用的模拟算法，用数组来做的，当连续m个值为0时就把那个数组元素置为count，count表示第几个出列的。所以当count==N时就知道它是最后一个人。

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std ;
int main()
{
	vector<int> a;
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	a.push_back(0);
	
	int i=0;
	int j=1;
	int count=0;
	while(1)
	{
		
		if(count==m&&count!=0)
		{
			count=0;
			if(i==0)
			a[n-1]=j;
			else	
			a[i-1]=j;
			
			if(j==n)
			{
				if(i==0)
				cout<<n;
				else
				cout<<i;
				break;
			}
			
			j++;
		}
		
	
		if(a[i]==0)
		count++;
		i=(i+1)%n;
		
	}
	

	return 0;
}

但是这样子的模拟算法对于小量数据可行，大量数据就给超时了。因为当N非常大时，M也非常大，要找最后两个人谁出列，这样一来大约就要遍历 N*M 次，这就非常复杂了。所以下面我们用数学递推公式：

f(1) = 0

f(n) = (f(n-1)+m)%n (n>1)

公式中编号从0开始，所以题目中的答案是f(n)+1

详细推导过程  ： http://book.51cto.com/art/201403/433941.htm

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std ;

int f(int n,int m)
{
	if(n==1)
	return 0;
	
	return (f(n-1,m)+m)%n;
}

int main()
{
	vector<int> a;
	int n,m;
	cin>>n>>m;
	
	cout<<f(n,m)+1;
	return 0;
}