如何用 Ruby 语言搞定小学三年级的奥数题?

儿子小学三年级,参加奥数培训。拿一道题目来向我求助:


房间里面有 200 盏灯泡,依次编号 1……200,每一盏灯泡都由一个独立的开关控制,开始时所有灯泡都是关着的。现在将所有编号能够被 1 整除的灯泡的开关按一下,然后将所有编号能够被 2 整除的灯泡的开关再按一下,然后将所有编号能够被 3 整除的灯泡的编号按一下,一直重复 200 遍,最后将所有编号能够被 200 整除的灯泡的开关按一下。请问,最后,房间里面有几盏灯是亮着的? 


题目看完了,我心里咯噔一下:


尼玛,这题目是给三年级小孩做的吗?我也不会哇!


不过,在儿子面前不能这么轻易服软。于是对儿子说,这道题目挺难的,我先思考一下,你先去玩一会儿游戏。儿子很开心的种植物打僵尸去了。 


似乎没有什么好算法,我先找几个灯泡试试看:


编号为 1 的灯泡,开关总共被按了一次,所以最后是亮着的;


编号为 2 的灯泡,开关总共被按了两次,所以最后是灭了;


编号为 3 的灯泡,开关总共被按了两次,所以最后也是灭的;


编号为 4 的灯泡,开关总共被按了三次,所以最后是亮着的;


编号为 5 的灯泡,被按了两次,所以最后是灭的;


嗯……如果编号是个质数,灯泡就是灭的;


编号为 6 的灯泡,开关被按了 4 次,最后也是灭的;


你妹啊,这个 6 不是质数,也是灭的,这可如何是好?继续看看吧……


编号为 7 的灯泡,最后是灭的;


编号为 8 的灯泡,可以被 1、2、4、8 整除,按了四次,也是灭的;


编号为 9 的灯泡,按了 3 次,最后是亮着的;


嗯……现在快到 10 了,第 1/4/9 号灯泡是亮着的,其它都是灭的;难道,所有编号是“平方数”的灯泡,最后都是亮着的,其它则都灭了?凭直觉,感觉应该就是这样的。


如果编号为 N 的灯泡的开关,被操作了奇数次,那么最后它就是亮的,如果是偶数次,那么就是灭的。实际上这个题目就转换为:给定一个自然数 N,区间 [1,N] 中能够整除 N 的自然数的个数,在什么情况下是奇数?在什么情况下是偶数?


假设 N = m*n,m 和 n 都是自然数,且 m≤n,显然 N 可以被 m 和 n 同时整除;假设 N 的平方根为 q,那么:


1. 如果 q 不是整数,那么必有 m∈[ 1 , q ),n∈( q , N ],m 和 n 是成对出现的,能够整除 N 的自然数,一定是偶数个;


2. 如果 q 是整数,那么能够整除 N 的自然数,就会在上一条成对出现的因子数量基础上,再加一个 q,所以就有奇数个因子。


200 以内有多少个平方数,就有几盏灯亮着了,原来如此,还是挺简单的嘛

 

为了方便儿子理解,我决定先给他看最后结果,再反过来引导他分析原因。作为一个挨踢人士,现在我正在用 Ruby 语言教儿子编程起步知识,于是就想写一个程序,来模拟操作灯泡,对所有的灯泡穷举一遍,顺便来教儿子 Ruby 语法,于是打开笔记本,写了一个简单的 Ruby 脚本。脚本如下:



先给儿子逐行讲解了这个脚本。因为以前给他讲过一些简单的 Ruby 入门知识,所以现在他理解起来也不是完全听不懂。他兴致勃勃半懂不懂的听完之后,迫不及待的执行了一遍,输出如下:



他很快就发现了“平方数”灯泡亮着的规律,但是在独立思考为什么只有平方数灯泡才亮着的问题时,就卡壳了。于是我就只能引导他一步步的去分析。还好,很快也弄明白了。然后,他又反复修改灯泡的总数量,反复执行,连连赞叹:哇,Ruby 这个东西真是个超级牛逼的东西;最喜欢的植物大战僵尸也暂时扔到一边去了。




 作者介绍  


雷雨后


现在任职于华为网络产品线,从事过开发,从事过测试,现在专注于研发工具与研发能力。


用过 C、用过 C++、钻研过 TCL/Tk、Ruby、R。喜欢研究各种编程语言,喜欢各类软件工具,喜欢 IT 中的一切新鲜事物。


著作远远还未等身:一部大部头的《Tcl 脚本语言》和《Tcl 高级进阶》,百度文库可以免费下载;一篇中部头的《CppUnit 和 MockPP 单元测试指导书》,公司内还有人在传阅。


华为网络产品线的测试自动化语言,在我的努力下,切换到了Ruby;做过一些广泛使用的工具和框架:Impeller、TDL、SmartIDE 等。现在在钻研 ADLM、智能研发、大数据等。


很惭愧,也就做了一点点微小的工作。



往期精华文章  

微信公众号中回复数字查看更多精华文章:


回复【1】:技术干货

回复【2】:程序员幽默世界

回复【3】:物联网江湖

回复【4】:华为招聘

回复【5】:HDG 视频+PPT 汇总

回复【6】:华为开发者大赛获奖作品展示

相关文章
相关标签/搜索