小明特别喜欢开关灯。
现在有编号为1~100的灯初始状态是全开着的,现进行如下操作:
- 编号是1的倍数的灯拨一下开关;
- 编号是2的倍数的灯再拨一下开关;
- 编号是3的倍数的灯再拨一下开关;
- …………
- 如此直到100的倍数。
问:此时还有多少盏灯仍然是开着的。
这个问题很简单,它其实就是在问:1~100中,有多少约数个数为偶数的数字。(偶数次操作的效果是没变化)
然后把这个分析翻译成C程序代码:
#include<stdio.h>
#define NUM 100
int main(){
int n=0;
for(int i=1;i<=NUM;i++){
int p=0;
for(int j=1;j<=i;j++)
if(i%j==0) p++;
if(p%2==0) n++;
}
printf("%d\n",n);
return 0;
}
这样很快地就可以得到结果90,之后就结束了吗?
不,这个解法是比较傻的,比较慢的——试着换个加强版的问题:
87654321盏灯!
小明现在有87654321盏灯⊙﹏⊙b汗。
现在有编号为1~87654321的灯初始状态是全开着的,现进行如下操作:
- 编号是1的倍数的灯拨一下开关;
- 编号是2的倍数的灯再拨一下开关;
- 编号是3的倍数的灯再拨一下开关;
- …………
- 如此直到87654321的倍数。
问:此时还有多少盏灯仍然是开着的。
还按刚才的解法来?(对代码稍作修改)
#include<stdio.h>
#define NUM 87654321//改个数
int main(){
int n=0;
for(int i=1;i<=NUM;i++){
int p=0;
for(int j=1;j<=i;j++)
if(i%j==0) p++;
if(p%2==0) n++;
}
printf("%d\n",n);
return 0;
}
运行起来时间似乎有点长啊。(我不想等下去了)那要怎么办?
回到问题上来:约数个数为偶数的数字有什么特点,或者说,约数个数为奇数的数字有什么特点?
从1,2,3,4,5,6,7,8,9,10,……下手,会发现:约数个数为奇数的数字是1,4,9,……这些完全平方数。
所以大幅更新一下代码:
#include<stdio.h>
#include<math.h>
#define NUM 87654321
int main(){
int n=NUM;
for(long i=1;i<=NUM;i++){
int r=(int)sqrt(i);
if(r*r==i) n--;
}
printf("%d\n",n);
return 0;
}
这样就能在一个较为合理的时间内得到答案87644959了,不过还是不够快。
于是再想一下,得到的终极代码是:
#include<stdio.h>
#include<math.h>
#define NUM 87654321
int main(){
int n=NUM;
printf("%d\n",n-(int)sqrt(n));
return 0;
}
这样甚至可以用纸笔解得答案。
所以说,虽然编程这项技能的确可以帮助我们思考问题、解决问题,但归根结底,思维才是最关键的。(别因为有了电脑,废了人脑)
网友评论