Question

利用C++应该怎么解决“约瑟夫问题”？

Answer 1

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

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

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

Answer 2

#include<iostream>

using namespace std;

int a[10010]; //数组的值代表是否出局 

int main()

{

int n,m,f,s,t;// n为总人数，m为报的数，f为计数器

              //s为出局人数 

cin>>n>>m;

f=s=0;

t=1;

while(s<n-1)  //当出局人数为n-1的时候结束循环； 

{

if(a[t]==0) f++;//状态为0，说明未出局，第t个人报数

if(f==m)

{

cout<<t<<"　";

a[t]=1;//第t个人标记出局 

s++; //出局人数加1 

f=0;//计数器清0 

} 

t++;//位置往下移 

if(t>n) t=1;  //当m>n时，报数到n之后，从第一个开始 

}

return 0;

}