C语言程序设计100例之（17）：百灯判亮

例17   百灯判亮

问题描述

有序号为1、2、3、…、99、100的100盏灯从左至右排成一横行，且每盏灯各由一个拉线开关控制着，最初它们全呈关闭状态。有100个小朋友，第1位走过来把凡是序号为1的倍数的电灯开关拉一下；接着第2位小朋友走过来，把凡是序号为2的倍数的电灯开关拉一下；第3位小朋友走过来，把凡是序号为3的倍数的电灯开关拉一下；如此下去，直到第100个小朋友把序号为100的电灯开关拉一下。问这样做过一遍之后，哪些序号的电灯是亮着的？

输入格式

每行测试数据是一个正整数n，代表第n盏灯。

输出格式

每行输出第n盏灯的状态，0代表灯是熄灭的，1代表灯是亮的。

输入样例

1

5

输出样例

1

0

        （1）编程思路1。

        要判定哪些序号的灯是亮的，需要知道100个小朋友操作过后，每盏灯的拉线开关被拉的次数，这样凡是被拉了奇数次开关的灯最后就是亮的。

        为了保存每盏灯的拉线开关被拉的次数，需要定义一个一维数组int  a[101]；用数组元素a[1]~a[100]保存1~100号灯的开关被拉的次数（初始值为0，表示开关没有被拉1次）。

        程序用一个二重循环来模拟小朋友的操作过程。外循环控制小朋友从1~100，对于第i个小朋友，他拉第i、2i、3i…号灯的拉线开关的操作构成内循环。具体描述为：

         for (child=1;child<=100;child++)               // 小朋友从1~100

               for (lamp=child;lamp<=100;lamp+=child)    // 第i个小朋友从第i号灯开始操作

                     a[lamp]++;

        经过循环模拟小朋友拉开关的动作后，判定元素a[i]的奇偶性，如果a[i]为奇数，则第i盏灯是亮的。

        （2）源程序1。

#include <stdio.h>

int main()

{

    int a[101],child,lamp;     // a[1]~a[100]保存1~100盏灯的开关被拉的次数

    for (lamp=0;lamp<=100;lamp++)

        a[lamp]=0;

    for (child=1;child<=100;child++)

       for (lamp=child;lamp<=100;lamp+=child)

           a[lamp]++;

    int n;

    while (scanf("%d",&n)!=eof)

    {

       if (a[n]%2)

           printf("1\n");

       else

           printf("0\n");

    }

    return 0;

}

         （3）编程思路2。

        实际上，除了采用思路1的方式用数组直接模拟外，本例还可以这样做。

        我们知道，第n盏灯的拉线开关只会由编号为其约数的小朋友拉一下。例如，第24盏灯，会由编号分别为1、2、3、4、6、8、12、24的小朋友拉一下，它被拉了偶数次，故它最终是熄灭的。

        更一般地，对于第n盏灯，若n=i*j，则一定有编号为i的小朋友的操作将灯由0变成1，编号为j的小朋友的操作会将灯由1变成0。最后，当且仅当n=i*i时，灯是亮的。

        因此，本题实质是判断n是否是完全平方数即可。

        （4）源程序2。

#include <stdio.h>

#include <math.h>

int main()

{

    int n,k;

    while (scanf("%d",&n)!=eof)

    {

       k=(int)sqrt(1.0*n);

       if (k*k==n)

           printf("1\n");

       else

           printf("0\n");

    }

    return 0;

}

习题17

17-1  the drunk jailer

        本题选自北大poj题库（http://poj.org/problem?id=1218）

description

a certain * contains a long hall of n cells, each right next to each other. each cell has a *er in it, and each cell is locked.

one night, the jailer gets bored and decides to play a game. for round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. for round 2, he takes a drink of whiskey, and then runs down the

hall locking every other cell (cells 2, 4, 6, ?). for round 3, he takes a drink of whiskey, and then runs down the hall. he visits every third cell (cells 3, 6, 9, ?). if the cell is locked, he unlocks it; if it is unlocked, he locks it. he

repeats this for n rounds, takes a final drink, and passes out.

some number of *ers, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. they immediately escape.

given the number of cells, determine how many *ers escape jail.

input

the first line of input contains a single positive integer. this is the number of lines that follow. each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

output

for each line, you must print out the number of *ers that escape when the * has n cells.

sample input

2

5

100

sample output

2

10

        （1）编程思路。

        本题与例17本质上是同类型的题，只是最终输出不一样。按例17的两种思路可以编写源程序1和2如下。

        （2）源程序1。

#include <stdio.h>

int main()

{

     int t,n,i,j,cnt,a[101]={0};

    scanf("%d",&t);

    for (i=1;i<=100;i++)

          for (j=i;j<=100;j+=i)

                  a[j]=1-a[j];

   while (t--)

   {

        scanf("%d",&n);

         cnt=0;

         for (i=1;i<=n;i++)

              if (a[i]==1) cnt++;

         printf("%d\n",cnt);

     }

    return 0;

}

        （3）源程序2。

#include <stdio.h>

#include <math.h>

int main()

{

         int t,n;

        scanf("%d",&t);

        while (t--)

         {

                   scanf("%d",&n);

                   printf("%d\n",(int)sqrt(1.0*n));

         }

         return 0;

}

17-2  开灯

        本题选自洛谷题库 （https://www.luogu.org/problem/p1876）

题目描述

首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是1的倍数的灯全部打开；编号为2的人把是2的倍数的灯全部关上；编号为3的人又把是3的倍数的灯开的关上，关的开起来……直到第n个人为止。

给定n，求n轮之后，还有哪几盏是开着的。

输入格式

一个数n（1<=n<=2^40），表示灯的个数和操作的轮数。

输出格式

若干数，表示开着的电灯编号

输入样例

5

输出样例

1 4

        （1）编程思路。

        本题中n的值可能很大，因此采用例1中的思路1用数组模拟肯定会超时，因此只能采用思路2的做法。通过判断正整数i（1<=i<=n）是否为完全平方数，决定编号为i的灯是否是开着的。

        （2）源程序。

#include <stdio.h>

int main()

{

   long int i,n;

   scanf("%ld",&n);

   for (i=1;i*i<=n;i++)

       printf("%ld ",i*i);

   return 0;

}

17-3  又是开灯

        本题选自洛谷题库 （https://www.luogu.org/problem/p1161）

题目描述

在一条无限长的路上，有一排无限长的路灯，编号为1,2,3,4,…。

每一盏灯只有两种可能的状态，开或者关。如果按一下某一盏灯的开关，那么这盏灯的状态将发生改变。如果原来是开，将变成关。如果原来是关，将变成开。

在刚开始的时候，所有的灯都是关的。小明每次可以进行如下的操作：

指定两个数，a,t（a为实数，t为正整数）。将编号为[a],[2×a],[3×a],…,[t×a]的灯的开关各按一次。其中[k]表示实数k的整数部分。

在小明进行了n次操作后，小明突然发现，这个时候只有一盏灯是开的，小明很想知道这盏灯的编号，可是这盏灯离小明太远了，小明看不清编号是多少。

幸好，小明还记得之前的n次操作。于是小明找到了你，你能帮他计算出这盏开着的灯的编号吗？

输入格式

第一行一个正整数n，表示n次操作。

接下来有n行，每行两个数a,t，其中a 是实数，小数点后一定有6位，t是正整数。

输出格式

仅一个正整数，那盏开着的灯的编号。

输入样例

3

1.618034  13

2.618034  7

1.000000  21

输出样例

20

说明/提示

数据保证，在经过n次操作后，有且只有一盏灯是开的，不必判错。

        （1）编程思路。

         本题如果采用例17的思路1进行模拟不是一种恰当的解法。首先题目中没有说明数据范围，只说“在一条无限长的路上，有一排无限长的路灯”，因此定义数组元素的个数需要斟酌；另外，n次操作，每次操作若干盏灯，模拟下来也可能会超时。因此，需要想出其他更简便的解决方法。

        注意到题目的提示“在经过n次操作后，有且只有一盏灯是开的”。也就是说n次操作中除了一盏灯被按的次数是奇数次外，其余编号的灯被按的次数一定是偶数次。

以样例给出的数据为例：

第1次，“1.618034  13”，编号为1,3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21这13盏灯的开关会被按一下；

第2次，“2.618034  7”，编号为2，5，7，10，13，15，18这7盏灯的开关会被按一下；

第3次，“1.000000  21”，编号为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21这21盏灯的开关会被按一下。

可以看出除了编号20的灯外，其余编号均出现偶数次，即两两会成对出现。

        异或运算有一个特性：数x与自身异或其值一定为0，而0和x异或结果为x。因此，将上面的表示灯的编号的41个数全部异或起来，结果一定是答案。因为根据题目的提示“在经过n次操作后，有且只有一盏灯是开的”可知，除一盏灯外，其余灯的编号一定两两出现，异或后一定为0。

        （2）源程序。

#include <stdio.h>

int main()

{

       int n,t,i,ans;

       double a;

       scanf("%d",&n);

       ans=0;

      while (n--)

      {

             scanf("%lf%d",&a,&t);

             for (i=1;i<=t;i++)

                  ans=ans^((int)(a*i));

      }

     printf("%d\n",ans);

    return 0;

}