现在的位置: 首页 > 综合 > 正文

约瑟夫环问题

2013年01月22日 ⁄ 综合 ⁄ 共 626字 ⁄ 字号 评论关闭

题目:

n 个数字(0,1,…,n-1)形成一个圆圈,从数字0 开始,每次从这个圆圈中删除第m 个数字(第一个为当前数字本身,第二个为当前数字的下一个
数字), 当一个数字删除后,从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字。

该题目是以下题目的变形。

(n 个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),
凡报到3的人退出圈子,问最后留下的是原来第几号的那个人?)

个人感觉值得注意的是:n个数字是0,1,…,n-1,而不是1,…,n。

 

#include <iostream>
using namespace std;

int Yuese(int m, int n)//法一
{
	int a[50],count=0,k=0;
	for(int i=0; i<n; i++)
		a[i]=i+1;

	i=0;
	while(count<n-1)
	{
		if(a[i])
			k++;
		if(k==m)
		{
			a[i]=0;
			k=0;
			count++;
		}
		i++;
		if(i==n)
			i=0;
	}

	i=0;
	while(!a[i])
		i++;
	return i;
}

int Yuese2(int m, int n)//法二
{
	int temp=0;
	for(int i=2; i<=n; i++)
		temp=(temp+m)%i;
	return temp;
}

void main()
{
	int n, m;
	cin>>n>>m;
	cout<<Yuese(m, n);
	cout<<Yuese(m, n);

}

参见:http://blog.csdn.net/v_JULY_v

抱歉!评论已关闭.