这里补充一下约瑟夫问题的描述：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;
}
温馨提示：内容为网友见解，仅供参考
第1个回答 2013-11-19
这是以前写的一个用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;
}
附图:本回答被网友采纳
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;
}
附图:本回答被网友采纳
相似回答
