例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 prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner 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 prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.
Given the number of cells, determine how many prisoners 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 prisoners that escape when the prison 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61757.html
標籤：C