有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位。
输入
初始人数n
输出
最后一人的初始编号
样例输入复制
3
样例输出复制
2
思路:约瑟夫环问题,需要考虑:1.成环(即当遍历到最后一个时,让他下一个为初始)
2.标记问题,代表退出
3.结束条件:本题为剩最后一人。
实现:for循环,无判别条件(即为无限循环),由循环内条件控制循环结束。成环问题。及最后 寻找问题(剩余最后一人,特判标记(1)。每次退出的人直接打上标记。(0))
代码:
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[1000],i,c,flag=0;
c=n; //代替人数变量进行变化,控制循环
for (i=1; i<=n; i++)
a[i]=1; //标记。
for (i=1;;i++){
if (i==n+1)
i=1;//如果i超出了n个人,让他重新回到1 (围圈)
if (a[i]!=0) // 如果人在圈内
flag++; // 报数加1
else
continue;
if (flag%3==0){//报3退出。
a[i]=0; // 退圈
c--;// 人数--
}
if (c==1)//表示只剩下一个人在圈内
break;
}
for (i=1; i<=n; i++)
if (a[i]!=0)
c = i;
cout<<c;//输出第几个人
return 0;
}