@EncyKe
2016-10-26T02:52:32.000000Z
字数 3230
阅读 2427
#手记
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 三种语言以及纯数学解法来解这一问题。
当时面试官就给 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();
面试官也肯定了我的上述思路,然后,他慢悠悠地提出了一个我猜到他紧接着会提出的——就算他不提,回来我也会想一番的——问题:「那若是 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);
我预料了面试官会问扩展性的问题,我把传入形参的想法讲了讲。但我倒没预料他接下来的一个问题:「那,有没有想过纯数学解法?」
这,是不是大学毕业生和高中生的区别呢?现在一抄起白纸和笔都能手写代码解决,居然没考虑用纯数学解法?
面试官看得出我没有考虑过,于是也饶有兴趣地引导我——
「你看,100 号人轮流经过,某盏编号为 n 的灯能不能被摸,就取决于人的编号 m 能不能被 n 整除,对吧?」
「嗯。」「那是不是编号 n 的灯只会被编号是 n 的公约数的所有人去摸?」
「嗯,对。」「那是不是就是灯的编号 n 有多少个公约数,它就会被摸几次?而且最后要是亮着的,则被摸的次数、即 n 的公约数必须是奇数个?」
「没错。」「那就变成求 100 以内的公约数为奇数个的数字,这是一类很特别的数字,你知道的什么了吧?」
「哦!!!!」(但我当时思路是有点跟不上的,一片懵逼状,一时还没想出来,只能哦一哦表示神奇)。
你现在知道 公约数为奇数个 的一类神奇的数字是什么了吧?懒得想的话就 run 上面的代码召唤神龙咯。
我当时二话不说就用了初恋女友去解。回来以后,举一反三,用我代码路上邂逅的另一位优雅、知性的熟女姐姐——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)
那当你用知性熟女 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;
}
综上,个人觉得——
range()
、power()
等的数据处理函数,也有各种现成的高效的库可作为依赖,对于这类算法、统计、数据处理等场景是十分适用的;