华师一附中OI组

标题: 开关灯问题 [打印本页]
作者: admin    时间: 2020-2-12 10:42
标题: 开关灯问题
一个房间有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    时间: 2020-2-12 11:09
第二种方法：

  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2