保函网

利用C解决约瑟夫问题。

发布时间：2025-11-23 | 来源：互联网转载和整理

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

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

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

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

代码如下：

#includeusingnamespacestd;intmain(){intm,n,i,s=0,rem;//s为计数器,rem为剩余人数int*a;cout>n>>m;rem=n;a=newint[n];for(i=0;i1){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;}ｄｅｌｅｔｅ[]a;return0;}