百度100盏灯问题
Q:
有100盏灯泡,第一轮点亮所有电灯,第二轮每两盏灯熄灭一盏,即熄灭第2盏,第4盏,以此类推,
第三轮改变编号为3的倍数的电灯,第3盏,第6盏,如果原来那盏灯是亮的,就熄灭它,如果原来是灭的,
就点亮它,以此类推,直到第100轮。问第100结束后,还有多少盏灯泡是亮的?
A:
1.对于每盏灯,拉动的次数是奇数时,灯就是亮着的,拉动的次数是偶数时,灯就是关着的。
2.每盏灯拉动的次数与它的编号所含约数的个数有关,它的编号有几个约数,这盏灯就被拉动几次。
3.1——100这100个数中有哪几个数,约数的个数是奇数。我们知道一个数的约数都是成对出现的,
只有完全平方数约数的个数才是奇数个。
所以这100盏灯中有10盏灯是亮着的。
它们的编号分别是: 1、4、9、16、25、36、49、64、81、100。
#include<iostream> using namespace std; void bulb100() { int i,j; int TimesOfOnOFF[101]={0};//记录100盏灯的开关次数 for(i=1;i<=100;i++) //外部循环 序号为i倍的灯开关一次 { for(j=1;j<=100;j++) //依次遍历100盏灯 { /*注意:排除非零倍情况 j>=i*/ if(j>=i&&j%i==0) //如果灯的序号是i的倍数(非0倍)则开关一次,增加该序号灯的开关记录 TimesOfOnOFF[j]++; } } cout<<"the bulbs stayed on is as follow:"<<endl; for(j=1;j<=100;j++) { if(TimesOfOnOFF[j]%2==1) //开关次数为奇数的,则最终为亮状态 cout<<j<<" "; } } /*问题拓展为1000盏灯的问题*/ void bulb1000() { int i,j; int TimesOfOnOFF[1001]={0};//记录1000盏灯的开关次数 for(i=1;i<=1000;i++) //外部循环 序号为i倍的灯开关一次 { for(j=1;j<=1000;j++) //依次遍历1000盏灯 { /*注意:排除非零倍情况 j>=i*/ if(j>=i&&j%i==0) //如果灯的序号是i的倍数(非0倍)则开关一次,增加该序号灯的开关记录 TimesOfOnOFF[j]++; } } cout<<"the bulbs stayed on is as follow:"<<endl; for(j=1;j<=1000;j++) { if(TimesOfOnOFF[j]%2==1) //开关次数为奇数的,则最终为亮状态 cout<<j<<" "; } } int main() { cout<<"bulb100 \n\n"; bulb100(); cout<<"\n\nbulb1000 \n\n"; bulb1000(); cout<<"\n\n \n\n"; return 0; } /********************************* 程序运行情况如下: bulb100 the bulbs stayed on is as follow: 1 4 9 16 25 36 49 64 81 100 bulb1000 the bulbs stayed on is as follow: 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 Process returned 0 (0x0) execution time : 0.047 s Press any key to continue. **********************************/