题目相关
题目描述
有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。
输入
初始人数n
输出
最后一人的初始编号
分析
在读完题目发现，这道题目就是需要我们模拟循环报数的过程，可以想象一下小时候玩击鼓传花时候的情景。这道题目的难点在于如何判断某个同学是不是还在队伍中，不是简单的判断是否是3的倍数，这种方法，仅适用于不循环的报数，一旦首尾相连，倍数的判断就不太合适了。
构造数组表明学生的状态
每个同学在这道题目中的数据信息有两个，学号（编号），是否在队伍中（在/不在）。如何采用一定的方法，将这两者结合起来则能迅速处理这一问题。此时，我们可以构造一个标记数组，将这两者结合起来。将数组的下标作为学生学号，存储的内容用来表示学生状态。共有两个状态，我们可以使用布尔类型(bool)数组分别用true和false来表示两种状态，也可以使用整数类型数组表示对应状态,为了方便从下标1开始，开辟空间时可开辟人数+1的空间。
//开辟bool类型数组stu，用来表示各个学生的状态
//stu[x] 为true 表示报到了3不在队伍中， false 表示还在队伍中
bool *stu = new bool[n + 1];// n 为学生人数
利用取余实现模拟循环
该题的另一个难点在于怎么进行循环?无论是 从1~3反复进行报数还是，n个同学围成一圈，都涉及到了这一点。一种方法是判断，当判断到结尾时，将值重新改成开头。类似下面这样
if(num==3) num=1;
if(i==n) i=1;
但这么写有些麻烦，也得需要考虑变化过程对他的影响。这事我们可以考虑另一种方法，使用取余符号(%)进行模拟。
已知%符号的作用是获取余数，例如 7%5=2。当能整除时，结果为0。所以当一个数字%n时，结果一定在0~n-1之间。并且当a%b,a<b时，a%b=a。利用这些特性可以写出这样的一个式子:x=(x+1)%n ,这样x能变成x+1；当x为n-1时，x会变成0，不断重复x就能在0n-1之间循环。若想在1n之间循环可以修改成x=x%n+1。
int i = 1; //学生的学号 1~n
while (ren > 1) //循环报数，直到剩下一个人
{
if (stu[i] == false) // 如果在队伍中
{
num = num % 3 + 1; //报数
if (num == 3)
{ //报到3
stu[i] = true; //退出队伍
ren--; //在队伍中的人数减一
}
}
i = i % n + 1; //下一个学生的编号
}
枚举法找出最后剩下的人的编号
最后只剩下最后一人，必定是这样的状态:所有人都是true,只有他是false。那么我们只需要枚举遍历下，找出状态为false的即可。
for (int j = 1; j <= n; j++)
{//枚举学号1~n的同学
if (stu[j] == false)
{//当状态为false,则说明j在队伍中
cout << j;//输出编号
break;//结束循环
}
}
代码实现
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
//n-存储人数 num-报的数字 ren-留下的人数
int n, num = 0, ren;
cin >> n; // 输入在人数
ren = n; //确定在队伍中的人数
//开辟bool类型数组stu，用来表示各个学生的状态
//stu[x] 为true 表示报到了3不在队伍中， false 表示还在队伍中
bool *stu = new bool[n + 1];
//初始化 stu,使初始值为false
memset(stu, false, sizeof(bool) * (n + 1));
int i = 1; //学生的学号 1~n
while (ren > 1) //循环报数，直到剩下一个人
{
if (stu[i] == false) // 如果在队伍中
{
num = num % 3 + 1; //报数
if (num == 3)
{ //报到3
stu[i] = true; //退出队伍
ren--; //在队伍中的人数减一
}
}
i = i % n + 1; //下一个学生的编号
}
for (int j = 1; j <= n; j++)
{//枚举学号1~n的同学
if (stu[j] == false)
{//当状态为false,则说明j在队伍中
cout << j;//输出编号
break;//结束循环
}
}
return 0;
}
做题时，可从全局角度出发，将题目分解成若干个小问题，解决后再整合起来。通过本题，可以练习数组的构造使用以及循环的处理。
