手记：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 出结果来。

/*
 * 计算编号为 n 的灯开关被触摸的次数 k；
 */
function getTurns(n){
  var k = 0;
  for (var i = 1; i <= 100; i++) {
    // 循环遍历 100 人，如若人次 i 能被灯号 n 整除，则计数、累加、返回；
    if (n % i === 0) { k++ }
  }
  return k;
}
/*
 * 计算 100 盏灯亮着的灯数 up；
 */
function getUps(){
  // 一开始亮着的灯数 up 为 0；
  var up = 0;
  for (var j = 1; j <= 100; j++) {
    // 循环遍历 100 盏灯，如若灯次 j 被触摸的次数不为偶数，说明最还是亮着的，则计数、累加；
    if (getTurns(j) % 2 != 0) {
        up++;
        console.log(j);
    }
  }
  // 输出亮着的灯数 up；
  return up;
}
getUps();

2.2. 扩展解法

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

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

/*
 * 计算编号为 n 的灯开关被触摸的次数 k；
 */
function getTurns(n, people){
  var k = 0;
  for (var i = 1; i <= people; i++) {
    // 循环遍历 people 个人，如若人次 i 能被灯号 n 整除，则计数、累加、返回；
    if (n % i === 0) { k++ }
  }
  return k;
}
/*
 * 计算总灯数为 lamps 时亮着的灯数 up；
 * 需传入灯数 lamps、人数 people；
 */
function getUps(lamps, people){
  // 一开始亮着的灯数 up 为 0；
  var up = 0;
  for (var j = 1; j <= lamps; j++) {
    // 循环遍历 lamps 盏灯，如若灯次 j 被触摸的次数不为偶数，说明最后是亮着的，则计数、累加；
    if (getTurns(j, people) % 2 != 0) {
        up++;
        console.log(j);
    }
  }
  // 输出亮着的灯数 up；
  return up;
}
getUps(100, 100);

2.3. 数学解法

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

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

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

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

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

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

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

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

3. Python解法

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

# -*- coding: utf-8 -*-
def getTurns(n, people):
  k = 0
  for i in range(1, people + 1):
    if n % i == 0:
      k += 1
  return k
def getUps(lamps, people):
  up = 0
  for j in range(1, lamps + 1):
    if getTurns(j, people) % 2 != 0:
      up += 1
      print j
  print up
getUps(100, 100)

4. C 语言解法

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

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

#include <stdio.h>
int main()
{
  int people, lamps, l, p;
    printf("Input lamps, pls.\n");
    scanf("%d", &lamps);
    printf("Input people, pls.\n");
    scanf("%d", &people);
  int a[lamps];
    int up = 0;
    printf("Those lamps that are still up are No.");
  for( l = 1; l <= lamps; l++ )
    {
    a[l] = 0;
    for( p = 1; p <= l; p++ )
        {
            if( l % p == 0 )
            {
        a[l]++;
            }
        }
        if( a[l] % 2 != 0 )
        {
      printf("%d, ", l);
            a[l] = 1;
            up = up + a[l];
        }
    }
    printf("\ntherefore there are still %d lamps that are up.\n",up);
    system("pause");
  return 0;
}

5. 小结

综上，个人觉得——

• Python 写起来确实简洁、大气、优雅，而且它自带诸多类似 range()、power() 等的数据处理函数，也有各种现成的高效的库可作为依赖，对于这类算法、统计、数据处理等场景是十分适用的；
• C 的运行快、性能较好，相对的代码量也较大，语法十分基础，感觉开发者的思路在 C 上可以延伸得比较广；
• JS 作为小妹妹，其实也只有我这种因为初恋情怀的前端切图仔才会用吧，但是运行不用太多环境，有个浏览器就行，现在哪台 PC/Mac 没有开着个现代浏览器呢？你只需 [F12]/[Command] + [Option] + [I]直接切入控制台就能写能用，对于小型的算法、难题，对我而言无疑是快速上手的解决方案；
• 至于纯数学解……去去去，代码拯救世界，天网时代都来了，你还扯什么纯数学解呢（嫌弃脸）。开开玩笑，没有基于纯数学的逻辑和思路，上述代码层面的东西都是不复存在的。