开灯问题

　　很多IT公司在面试的时候注重对面试者算法分析能力的考察，下面分析百度一道面试题并加以扩展。

有编号1~100个灯泡，起初所有的灯都是灭的。有100个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。如果灯是灭的，按过开关之后灯会亮。
现在开始按开关：
 第1个同学，把所有的灯泡开关都按一次(按开关灯的编号： 1,2,3,......100)。
 第2个同学，隔一个灯按一次(按开关灯的编号： 2,4,6,......,100)。
 第3个同学，隔两个灯按一次(按开关灯的编号： 3,6,9,......,99)。
 ......
 问题是，在第100个同学按过之后，有多少盏灯是亮着的？这些灯的编号是多少？要求给出解题思路或给出伪码。

算法分析：

　　设灯泡个数为m=100（编号1~100），按灯泡人数为n=100（同学1~100），灯泡亮记作状态1，灯泡暗记作状态0。按灯泡开关的情况概括为第i个同学按所有编号是i倍数的灯泡开关（即将关掉的灯泡打开，打开的灯泡关闭）。

　　1）数组arr[i]记录灯泡开关状态。第i个灯泡处于打开状态，则arr[i]=1；处于关闭状态，则arr[i]=0；

　　2）初始状态所有的灯都是熄灭的，因此初始状态arr[i]=0。

　　3）第一个同学比较特殊，是将所有的灯打开，即arr[i] = !arr[i]（最初arr[i]内元素均为0）；其余同学是灯泡是他们倍数的时候反转灯泡状态。

　　综上三点，我们发现这道题其实考察的知识点无非就是暴力搜索加模拟嘛，照着它给你的步骤依次做，分分钟解决!!!

伪代码：　　

 1 /* 灯泡状态初始化为0 */
 2 for m = 1 ~ 100:
 3     arr[m] = 0;
 4 
 5 /* 模拟开关灯泡操作 */
 6 for n = 1 ~ 100:
 7     for m = 1 ~ 100:
 8         if m mod n == 0:
 9             arr[m] = !arr[m];
10 
11 /* 输出最后亮灯泡的编号 */
12 for m = 1 ~ 100:
13     if arr[m]:
14         print arr[m];

C/C++程序代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #define  MAXN  100 + 10
 4 using namespace std;
 5 int arr[MAXN];
 6 
 7 int main()
 8 {
 9     int m = 100;   // 灯泡
10     int n = 100;   // 同学
11     memset(arr, 0, sizeof(arr));   /* 数组arr清零 */
12     
13     /* 模拟开关灯泡 */
14     for(int i = 1; i <= n; ++i) 
15     {
16         for(int j = 1; j <= m; ++j)
17         {
18             if(j%i == 0) 
19             {
20                 arr[j] = !arr[j];
21             }
22         }
23     }
24 
25     for(int i = 1; i <= 100; ++i)
26     {
27         if(arr[i]) 
28         {
29             printf("%d ", i);
30         }
31     }
32     
33     return 0;
34 }

开灯问题扩展(解答略)：

Description:有n盏灯，编号为1~n。第1个同学把所有灯都打开，第2个同学按所有编号为2倍数的的开关，第3个同学按所有编号为3的开关，依次类推。一共有k个人，问最后有哪些灯开着？

Input/Output:输入n和k，输出开着的灯编号。k<=n<=1000。

Case:输入7 3 输出 1 5 6 7

　　读者可以根据上面的分析自行解答。

本文系作者原创，转载请注明出处，谢谢合作。