题目
新年联欢晚会上,n个同学围成一圈(按照1~n给每个学生一个编号),第一个人从1开始依次报数,数到3的人出圈;再由下一个人重新从1开始报数,数到3的人出圈……;最后剩下的学生就是幸运使者,按照这个规则,你如果想成为幸运使者,你最开始应该站在几号位置。
【输入】
学生人数n。1<=n<=50;
【输出】
幸运使者的编号。
【输入样例】
25
【输出样例】
14
规律解析
出圈可能相对来说比较难理解,我们换种思维来思考就会更加清晰明了。我们假设所有的人都站起来,然后依次数数,数到m的人坐下,下一个人重新从1开始数,直到剩余最后1个人还没坐下,循环结束。
这样听起来是不是就会更加清晰。
我们定义一个数组,用来代表所有人的状态,数组中所有人初始为0代表站着,当她坐下时修改为-1。
定义当前数到数字多少 time_range,和剩下多少人还没坐下 out_number。
每次都是从数组的最前开始报数,先判断当前这个人是否站着 arr[i]==0,如果站着则让time_range++,然后再判断是否数到m,
当time_range==m的时候,代表这个人需要坐下,此时还需要的操作有:
1、站着的人数-1
2、修改当前人的状态为-1代表坐下
3、修改下一个该从0开始报数
当数到数组末尾时,我们需要从头开始再次遍历数组,直到站着的人数=1结束。
最后使用for循环遍历,找到唯一个arr[i]==0的,输出最后一个站的人的序号。
代码
#include<iostream>
#include<cstring>
using namespace std;int main(){//定义50人数组 因为从1开始编号所以数组长度为51 int arr[51];//人数 当前数到几 剩余出圈人数 int n,time_range=0,out_number;cin>>n;out_number=n;//初始化为0 0没出圈 -1出圈 memset(arr,0,sizeof(arr));//当剩余 出圈人数=1时,结束循环 否则不断重复从头到尾的循环遍历 while(out_number>1){for(int i=1;i<=n;i++){//每遍历一个检查是否为0 也就是未出圈 if(arr[i]==0){//数数加1 time_range++;//如果为3 则进行出圈操作 设为-1 剩余人数-1 重新数数 if(time_range==3){arr[i]=-1;out_number--;time_range=0;}}}}//遍历检查最后一个没出圈的 输出他的下标 for(int i=1;i<=n;i++){if(arr[i]==0){cout<<i;}}return 0;}