“喜欢开关灯的小明”问题

作者: yigoh | 来源:发表于2015-01-19 21:43 被阅读545次

    问题来源

    小明特别喜欢开关灯。

    现在有编号为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;
    }
    

    这样甚至可以用纸笔解得答案。

    所以说,虽然编程这项技能的确可以帮助我们思考问题、解决问题,但归根结底,思维才是最关键的。(别因为有了电脑,废了人脑)

    相关文章

      网友评论

      本文标题:“喜欢开关灯的小明”问题

      本文链接:https://www.haomeiwen.com/subject/bfkhxttx.html