题目相关

题目描述

有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就能在0_{n-1之间循环。若想在1}n之间循环可以修改成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;
}

做题时，可从全局角度出发，将题目分解成若干个小问题，解决后再整合起来。通过本题，可以练习数组的构造使用以及循环的处理。