返回首页 - Notes - 2012

开灯问题


问题描述

n 盏灯(编号为 1n),有 k 个人(k <= n

1 个人把所有开关按一遍(所有的灯都将开上),第 2 个人把编号为 2 的倍数的开关按一遍(对应编号的灯将熄灭),第 3 个人再把编号为 3 的倍数的开发按一遍(对应编号灯或熄灭或重开)。。。依次类推,直到 k 个人全部按完

现在输入 nk 的值,要求输出最后依然亮着的灯的编号


算法求解

问题求解的关键在于,怎么正确计算某个人按了哪些开关

代码如下:

#include <stdio.h>

int
main(int argc, char *argv[]){
    int n, k;

    scanf("%d%d", &n, &k);
    // 第一个下标不使用,所以数组大小多置一位
    int lamp[n+1];

    // 以按开关人的个数为外循环
    for(int i = 1; i <= k; ++i){
        // 以开关的个数为内循环
        // j总是从当前按开关人的编号开始
        for(int j = i; j <= n; ++j){
            // 第1个人把所有的灯开上
            if(1 == i){
                lamp[j] = 1;
            }else{
                // 其他人依次将对应的灯熄灭或重开
                if(0 == j%i){
                    lamp[j] *= -1;
                }
            }
        }
    }

    int flag = 1;
    for(int i = 1; i <= n; ++i){
        if(1 == lamp[i]){
            // 除第一个输出没有前导空格外,其他都有
            if(flag){
                flag = 0;
            }else{
                printf(" ");
            }
            printf("%d", i);
        }
    }

    return 0;
}

date : 2012-09-18