[关闭]
@EncyKe 2016-10-26T02:52:32.000000Z 字数 3230 阅读 1408

手记:100 盏灯谜题

#手记



1. 缘起

3 月初去面试时遇见过一道有意思的题目——

有 100 盏灯,编号依次为 1、2、3...100,电灯全部关着。开关摸一次为开,再摸一次即关。现在——
第 1 个人把所有编号为 1 的倍数(1、2、3...100)的灯的开关都摸了一次;
第 2 个人把所有编号为 2 的倍数(2、4、6...100)的灯的开关都摸了一次:
第 3 个人把所有编号为 3 的倍数(3、6、9...99)的灯的开关都摸了一次;
……
第 100 个人把第 100 号灯的开关摸了一次;

问:此时还有几盏灯亮着?它们的编号都是什么?

以下经由 JavaScript, Python, C 三种语言以及纯数学解法来解这一问题。

2. JavaScript 解法

2.1. 具体解法

当时面试官就给 10 分钟,一支笔一张白纸,然后他就什么都没说静静地去一旁等着我给出解答(出丑?装 X?)。

既然没有什么明确的要求,那么当一位程序猿看到题目、拿起白纸、经过思索之后肯定都是手写代码解决的啦。当时就用了最熟悉的我的初恋情人——JavaScript 来解决(而且又是去面前端的),代码如下(当然下面展示的代码段是经过后期整理、优化的,当天的手迹肯定很潦草,不过思路是完全一致的)。经测试放进控制台也能 run 出结果来。

  1. /*
  2. * 计算编号为 n 的灯开关被触摸的次数 k;
  3. */
  4. function getTurns(n){
  5. var k = 0;
  6. for (var i = 1; i <= 100; i++) {
  7. // 循环遍历 100 人,如若人次 i 能被灯号 n 整除,则计数、累加、返回;
  8. if (n % i === 0) { k++ }
  9. }
  10. return k;
  11. }
  12. /*
  13. * 计算 100 盏灯亮着的灯数 up;
  14. */
  15. function getUps(){
  16. // 一开始亮着的灯数 up 为 0;
  17. var up = 0;
  18. for (var j = 1; j <= 100; j++) {
  19. // 循环遍历 100 盏灯,如若灯次 j 被触摸的次数不为偶数,说明最还是亮着的,则计数、累加;
  20. if (getTurns(j) % 2 != 0) {
  21. up++;
  22. console.log(j);
  23. }
  24. }
  25. // 输出亮着的灯数 up;
  26. return up;
  27. }
  28. getUps();

2.2. 扩展解法

面试官也肯定了我的上述思路,然后,他慢悠悠地提出了一个我猜到他紧接着会提出的——就算他不提,回来我也会想一番的——问题:「那若是 n 盏灯、m 个人呢?」

对,身为一个以代码为工具解决战斗的人,你必须为你自己设计的工具预留一定的扩展性。2.1 具体解法 中的代码是写死的(限定 100 灯、100 人)、是比较粗暴野蛮的。而要有扩展性、可复用,解决方法也很简单,对上述代码进行小小改动,把灯数和人数作为形参传入,在实际调用的时候传入实参即可。

  1. /*
  2. * 计算编号为 n 的灯开关被触摸的次数 k;
  3. */
  4. function getTurns(n, people){
  5. var k = 0;
  6. for (var i = 1; i <= people; i++) {
  7. // 循环遍历 people 个人,如若人次 i 能被灯号 n 整除,则计数、累加、返回;
  8. if (n % i === 0) { k++ }
  9. }
  10. return k;
  11. }
  12. /*
  13. * 计算总灯数为 lamps 时亮着的灯数 up;
  14. * 需传入灯数 lamps、人数 people;
  15. */
  16. function getUps(lamps, people){
  17. // 一开始亮着的灯数 up 为 0;
  18. var up = 0;
  19. for (var j = 1; j <= lamps; j++) {
  20. // 循环遍历 lamps 盏灯,如若灯次 j 被触摸的次数不为偶数,说明最后是亮着的,则计数、累加;
  21. if (getTurns(j, people) % 2 != 0) {
  22. up++;
  23. console.log(j);
  24. }
  25. }
  26. // 输出亮着的灯数 up;
  27. return up;
  28. }
  29. getUps(100, 100);

2.3. 数学解法

我预料了面试官会问扩展性的问题,我把传入形参的想法讲了讲。但我倒没预料他接下来的一个问题:「那,有没有想过纯数学解法?」

这,是不是大学毕业生和高中生的区别呢?现在一抄起白纸和笔都能手写代码解决,居然没考虑用纯数学解法?

面试官看得出我没有考虑过,于是也饶有兴趣地引导我——

「你看,100 号人轮流经过,某盏编号为 n 的灯能不能被摸,就取决于人的编号 m 能不能被 n 整除,对吧?」
「嗯。」

「那是不是编号 n 的灯只会被编号是 n 的公约数的所有人去摸?」
「嗯,对。」

「那是不是就是灯的编号 n 有多少个公约数,它就会被摸几次?而且最后要是亮着的,则被摸的次数、即 n 的公约数必须是奇数个?」
「没错。」

「那就变成求 100 以内的公约数为奇数个的数字,这是一类很特别的数字,你知道的什么了吧?」
「哦!!!!」(但我当时思路是有点跟不上的,一片懵逼状,一时还没想出来,只能哦一哦表示神奇)。

你现在知道 公约数为奇数个 的一类神奇的数字是什么了吧?懒得想的话就 run 上面的代码召唤神龙咯。

3. Python解法

我当时二话不说就用了初恋女友去解。回来以后,举一反三,用我代码路上邂逅的另一位优雅、知性的熟女姐姐——Python 做了一番解答。下面只贴出扩展性的解法,思路一致,但结构和语句看起来可能更简约、更清晰一点。

  1. # -*- coding: utf-8 -*-
  2. def getTurns(n, people):
  3. k = 0
  4. for i in range(1, people + 1):
  5. if n % i == 0:
  6. k += 1
  7. return k
  8. def getUps(lamps, people):
  9. up = 0
  10. for j in range(1, lamps + 1):
  11. if getTurns(j, people) % 2 != 0:
  12. up += 1
  13. print j
  14. print up
  15. getUps(100, 100)

4. C 语言解法

那当你用知性熟女 Python 写完这则算法之后,你不由得想,祖母级别的 C 语言又表现如何呢?

所以我也作了尝试,不过在 C 语言的解法中,我的思路稍有不同。我把两个循环嵌套到一起,然后用类似桶排序的方式把灯编号写进一个数组的索引,而数组的值则对应其被摸过的次数,再将无法被 2 取模的值的索引打印出来,计数即可。

  1. #include <stdio.h>
  2. int main()
  3. {
  4. int people, lamps, l, p;
  5. printf("Input lamps, pls.\n");
  6. scanf("%d", &lamps);
  7. printf("Input people, pls.\n");
  8. scanf("%d", &people);
  9. int a[lamps];
  10. int up = 0;
  11. printf("Those lamps that are still up are No.");
  12. for( l = 1; l <= lamps; l++ )
  13. {
  14. a[l] = 0;
  15. for( p = 1; p <= l; p++ )
  16. {
  17. if( l % p == 0 )
  18. {
  19. a[l]++;
  20. }
  21. }
  22. if( a[l] % 2 != 0 )
  23. {
  24. printf("%d, ", l);
  25. a[l] = 1;
  26. up = up + a[l];
  27. }
  28. }
  29. printf("\ntherefore there are still %d lamps that are up.\n",up);
  30. system("pause");
  31. return 0;
  32. }

5. 小结

综上,个人觉得——

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注