Question

利用C++解决约瑟夫问题。

Answer 1

这里补充一下约瑟夫问题的描述：N个人围成一圈，从第一个开始报数，数到M的人出队，然后他的下一位继续从1开始报数，数到M的出队，如此循环直到剩下一个人，求最后剩下的那个人最初是队伍中的第几位。

解决这道题可以采用模拟报数的方法，建立一个大小为N的数组，数组的第N个元素表示第N个人是否还在队伍中，首先将每个元素都置为1，表示全员都在队伍中。如果第N个人出队，则将第N个元素置为0。

模拟报数可以使用一个累加计数器，用它表示这轮报数已有多少人报数，然后循环访问每个人，若其在队伍中，则将计数器+1，如果累加到M，则这个人出队。如此循环，直到N-1个人出队，仅剩1人。

最后遍历一下那个数组，找到还在队伍中的人就可以。

代码如下：

#include <iostream>

using namespace std;

int main()
{
	int m, n, i, s = 0, rem;	//s为计数器, rem为剩余人数
	int *a;
	
	cout << "输入总人数和出队的序号：" ;
	cin >> n >> m;
	rem = n;
	a = new int[n];
	for (i = 0; i < n; i++)
		a[i] = 1;
	i = 0;
	while (rem > 1)
	{
		s += a[i];
		if (s == m)			//第i个人出队，重置累加计数器
		{
			s = 0;
			rem--;
			a[i] = 0;
		}
		i++;
		i %= n;
	}
	for (i = 0; i < n; i++)
		if (a[i])
		{
			cout << "剩下的人为：" << i << endl;
			break;
		}
	delete []a;
	return 0;
}

Answer 2

这是以前写的一个用C++动态数组实现约瑟夫环问题. 有问题还请追问.程序如下:#include <iostream>
using namespace std;int main()
{
int n,m;
cout<<"输入玩家人数:";
cin>>n;
cout<<"输入报到哪个数会被淘汰:";
cin>>m; bool *a=new bool[n]; //定义玩家数组; int s=n,num=0; //s用于记录未被淘汰玩家的个数. num用于累加报数值.

for(int i=0;i<n;++i) //初始化玩家状态.
a[i]=true;

i=0; //下标重置.
while(i=i%n,1!=s)
{
if(a[i++] && ++num%m==0)
{
cout<<"第"<<i<<"位小孩被淘汰!"<<endl;
a[i-1]=false;
s--;
}
}

for(i=0;!a[i];++i); //寻找数组中胜利的玩家.
cout<<"\n第 "<<i+1<<" 位小孩胜利!"<<endl;

return 0;
}
附图: