开灯问题

题目

题目描述

有n盏灯，编号为1～n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？输入n和k，输出开着的灯的编号。k≤n≤1000。

样例输入：

1
7 3

样例输出：

1
1 5 6 7

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
using namespace std;

int main()
{
    /*
    1:开
    0:关
    */
    int n = 0, k = 0;
    cin >> n >> k;
    const int MAX = n;
    int a[MAX];

    for (int z = 0; z <= n - 1; z++)
    {
        //生成一个全是1的列表
        a[z] = 1;
    }

    for (int j = 0; j < n; j++)
    {
        for (int i = 1; i <= k; i++)
        {
            if (j % i == 0)
            {
                if (a[j] == 0)
                {
                    a[j] = 1;
                }
                if (a[j] == 1)
                {
                    a[j] = 0;
                }
            }
        }
        if (a[j] == 1)
        {
            cout << j << " ";
        }
    }
    return 0;
}

这个程序当然不能运行，它存在以下问题：

  1. 数组 a[MAX] 未正确初始化，可以改用vector。

  2. a 数组下标从 0 开始，但灯的编号从 1 开始，需要修正数组访问方式。

  3. 状态翻转逻辑错误，在翻转灯的状态时，不需要额外判断 a[j] == 0 或 a[j] == 1，直接 a[j] = !a[j]; 即可。

  4. 输出错误，在输出时，遍历 j 是 0 开始的，而灯的编号是 1～n，因此 cout << j; 需要 +1。

修正一下，顺便优化一下，就得到以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n + 1, 1); // 用1表示灯最开始是开的

    for (int i = 2; i <= k; i++)  // 从第2个人开始操作
    {
        for (int j = i; j <= n; j += i) // 每 i 个倍数翻转一次
        {
            a[j] = !a[j];  // 翻转状态
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 1)
        {
            cout << i << " ";
        }
    }
    return 0;
}

这就对了！