有n个人围成一圈,顺序排号,然后数数进行淘汰的解法和一些思考

时间:2023-01-06 17:24:49
有n个人围成一圈,顺序排号,然后数数进行淘汰的解法和一些思考

问题描述:

有n个人围成一圈,顺序排号。从第一个人开始报数(1~3报数),凡报到3的人退出圈子,问最后留下的人原来排在第几号。

分析:

首先由用户输入人数n,然后对这n个人进行编号【因为如果不编号的话,我们就不能知道最后是哪位童鞋留下来了:)】

然后就开始了一圈一圈的循环,不断形成新的圈子,不断有人被淘汰,那么循环到什么时候截止呢?对只剩最后一个人,也就是说淘汰n-1了个人的时候,这个时候停止循环。

在实际情况中,应该是这n个人一开始围成了一个大圈子,然后随着不断的淘汰,圈子不断减小,最后剩下的那个人的一开始的编号就是我们要的结果。

我在用数组来表示这些人,因为进行了初始化,所以数组中元素的值都是原来的编号,因此我们只需要将被淘汰的人对应的数组元素的值设置为0即可。然后随着不断的循环,最后只剩下一个值不为0的数组元素,这个元素就是我们要的结果。

程序代码:

#include<iostream>
#define MAXNUM 100
using namespace std;
int main()
{
int a[MAXNUM];
int n=0;//n表示一共多少人
int m=0;//m表示被淘汰的人数
int i=1;//每轮循环中的计数器
int k=0;//用来表示报数的数
int j=0;//用于循环的计数器
cout<<"请输入总人数:";
cin>>n;
//对数据进行初始化操作,给每个人进行编号
for(j=1;j<=n;j++)
{
a[j]=j;
}
//通过循环不断淘汰人,直到最后只剩下一个人
while(m < n-1)
{
if(a[i]!=0) //判断该人是否已经淘汰
{
k++;
}
if(k == 3)
{
a[i]=0; //淘汰报数为3的人(即将其值设置为0)
k=0;//将k置为0,重新报数
m++;//对淘汰人数进行计数
}
i++; //对下一个人进行判断
if(i == n+1) //到了圈子的末尾出处,下一个位置将是圈子的开始
{
i=1;//将下一个人置为 1(圈子的开始位置 )
}
}
for(j=1;j<=n;j++)
{
if(a[j]!=0)
{
cout<<"\n最后剩下的人原来的编号为:"<<a[j]<<" 的人\n"<<endl;
}
}
return 0;
}