题目描述
有 N 个小朋友围成一圈玩报数游戏,将小朋友编号为 1∼N,从 1 号开始进行 1,2,3 报数。
每当一个小朋友报到 3 时,该小朋友出局,下一个小朋友继续从 1 开始报数,直到所有小朋友出局为止。
请问,最后一个出局的小朋友的编号是多少?
例如,当 N=5 时,所有小朋友的出局顺序依次为 3,1,5,2,4。
输入格式
一行,一个整数 N。
输出格式
一行,一个整数,表示最后一个出局的小朋友的编号。
数据范围
1≤N≤100
样例
输入样例:
5
输出样例:
4
C++ 代码
#include<iostream>
using namespace std;
const int N=110;
bool st[N]; // st[i]表示第i+1位同学是否还在游戏中
/* 编号1~N映射到编号i:0~N-1,N~2N-1...,即每位同学编号为i%N+1 */
int main()
{
int n;
cin>>n;
int cnt=n; // cnt表示当前有多少位同学在游戏中
for(int i=0,j=0;cnt;i++) // 当cnt=0跳出循环
if(!st[i%n+1]) // 如果该同学还在游戏中
{
j++; // j计数
if(j==3) // 当j=3,有一位同学被退出游戏
{
st[i%n+1]=true; // i%n+1同学退出游戏
if(cnt==1) cout<<i%n+1<<' '; // 输出最后一位同学编号
j=0; // j变为0
cnt--; // 游戏总人数减少1
}
}
return 0;
}