《算法竞赛入门经典第二版》p39 开灯问题

企鹅不爱写代码！

583人浏览 · 2025-07-13 22:08:11

企鹅不爱写代码！ · 2025-07-13 22:08:11 发布

《算法竞赛入门经典第二版》p39 开灯问题

问题描述：有n盏灯，编号为1,2,⋯,n初始时，所有灯都是关闭的。有 n个人，第 1个人把所有灯都打开；第 2个人按下所有编号为 2的倍数的灯的开关（这些灯将被关闭）；第 3个人按下所有编号为 3的倍数的灯的开关（对于此时亮着的灯，按下后会关闭，对于此时关闭的灯，按下后会打开）；以此类推，直到第n个人按下编号为n的倍数的灯的开关。问最后有多少盏灯是亮着的？

这个题目的核心思路是：用一个一维数组存储每一盏灯是不是亮着的，是亮的我们就记为1，如果不是我们就记为0.

第一步：创建一个一维数组，然后将数组清零。

#include <stdio.h>
#include <string.h>
#define maxn 1010
int a[maxn];
int main()
{
    int n, k;               //一共有k个人，n盏灯
    memest(a, 0, sizeof(a));//memest函数可以高效快速的把数组清零，简洁好用
    scanf("%d%d", &n, &k);

补充一个知识点，将数组全部清空，也就是赋值为零：

我们可以使用初始化的方法`int a[100] = {0}`，但是对于这种`{0}`的办法只适用于初始化的时候

我们还可以使用循环的方法，一个个赋值，但是比较麻烦

但是我们使用`memest(要填充的内存的指针，需要赋值的值，该内存的总字节数)`函数就很方便

第二步：遍历所有的人，并且保存这些人操作后灯是亮的还是不亮的

    for (int i = 1; i <= k; i++)//从第一个人开始遍历到最后一个人，判断这个人需要操作哪一些灯
    {
        for (int j = 1; j <= n; j++)//从第一个灯开始遍历，看看外层循环的这个人需要操作的灯有哪些
        {
            if (j % i == 0)//找到外层循环的这个人需要操作的灯
            {
                a[j] = !a[j];//将这个灯的状态改变，数组a[]只会是0和1，通过非这种运算方式来运算
            }
        }
    }

第三步：输出结果

    int first = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i])
        {
            if (first)
            {
                first = 0;
            }
            else
            {
                printf(" ");
            }
            printf("%d", i);
        }
    }

这个地方大家肯定有疑问，为什么需要定义一个first，为什么不直接输出，为什么那么复杂？这个地方就涉及到一个输出结果的严谨性问题了，输出结果第一个位置是没有空格的，最后输出的一个数字的后面也是没有空格的，对于算法竞赛，特别是以后想参数ACM/ICPC类似的高质量的算法竞赛（蓝桥杯什么含金量懂得都懂，除了国赛），对于输出结果的检测特别严格，所以怎么控制第一个位置没有空格，最后一个也没有空格呢？

定义一个变量first，初始化为1

第一次循环，first==1，不输出空格，但是同时被赋值为0，后面的时候都会输出空格，最后一次执行完后，输出数字了，就不会再进循环体，所以最后没有空格

倘若大家以`" %d"`输出，第一个数字的前面会有空格，`"%d "`输出的话，最后就会多一个空格，所以上面的这种方法就是最优解

最后总体代码如下：

//开灯问题
#include <stdio.h>
#include <string.h>
#define maxn 1010
int a[maxn];
int main()
{
    int n, k;//一共有k个人，n盏灯
    memest(a, 0, sizeof(a));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (j % i == 0)
            {
                a[j] = !a[j];
            }
        }
    }
    int first = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i])
        {
            if (first)
            {
                first = 0;
            }
            else
            {
                printf(" ");
            }
            printf("%d", i);
        }
    }
}