开关灯问题

admin

一个房间有100个灯，每个灯对应着一个开关，按这个开关，灯的状态就发生改变，按之前是亮的灯按后就关了，之前是关的灯按之后就亮了，这和一般电视机或者遥控器上的开关是相似的，游戏前所有的灯都是关着的，第一个人进门把所有的开关都按了一次，所有的灯都开了，第二个人进来把所有2的倍数的开关按一下，所以偶数灯都熄了，以后每个人都这么做，第10个人按完后还有哪些灯是亮的？
我们用a(1)-a(100)的布尔数组来表示每个灯的亮灭情况，亮就a(i)=1，灭就a(i)=0;那么按一下就对应着a(i)=!a(i)，这个是编程世界里的常用技巧。
对于每个灯i，哪些人p会按到开关呢？通用两种表示方法：
1、从灯i来看，若j是i的约数，则被j按到了 for (j=1;j<=i;j++)if (i%j==1) a(i)=!a(i);
2、从人p来看，p*1 p*2等  j的倍数的灯被按到了 for (k=p;k<=100;k=k+p) a(k)=!a(k);
第二个效率略高一点，因为不用做那么多的除法。

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=100;
   
4. bool a[mn+5];
   
5. int i,p; ///i表示灯  p表示人
   
6. int main()
   
7. {
   
8.         for (i=1; i<=mn; i++) a[i]=0; ///假设每个等都是熄的
   
9.         for (p=1; p<=10; p++)  ///10个人
   
10.                 for (i=1; i<=mn; i++) if (i%p==0)a[i]=!a[i];
    
11.         for (i=1; i<=mn; i++) if (a[i]==1) cout<<i<<' ';
    
12.         return 0;
    
13. }

复制代码

admin

第二种方法：

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=100;
   
4. bool a[mn+5];
   
5. int i,p; ///i表示灯  p表示人
   
6. int main()
   
7. {
   
8.         for (i=1; i<=mn; i++) a[i]=0; ///假设每个等都是熄的
   
9.         for (p=1; p<=10; p++)  ///10个人
   
10.                 for (i=p; i<=mn; i=i+p) a[i]=!a[i];
    
11.         for (i=1; i<=mn; i++) if (a[i]==1) cout<<i<<' ';
    
12.         return 0;
    
13. }

复制代码