第四章 数学之趣

_2011-01-19_上午10.30.34.png
研究院的天井里有热带鱼、假山、午休的躺椅,也有人在讨论瓷砖覆盖地板的问题。

这一章列举了一些不须要写具体程序的数学问题,其中的原理和解决问题的思路对于提高思维能力还是很重要的。面试的时候,我们也会考察应聘者的数学分析能力。

在理论上,我们要严格地证明一些定理和结论。在实际工作中,则不必拘泥于此,例如,在“数独知多少”这一个题目中,纯数学的证明和推理可能需要相当多的时间。如果我们只需要求出大致的上界和下界就能解决实际问题,那也未尝不可。面试者在问这些看似很“难”的题目时,事实上是期望应聘者能够反问“这个问题一定是要精确的答案么?我能不能求出近似的解,然后再优化?”能这样反问,并且能够运用各种Heuristic(试探,探索的)方法快速求出解答的同学,我们非常欢迎。

本书的各位作者对数学的各个分支都不很熟悉,在这里班门弄斧,还希望能得到读者的指点。

我们把不好归类的几个题目也放到了本章,面试的类型多种多样,运用之妙,存乎一心。

一些人很担心这本书会把“题库”泄露出去,“那以后的面试就没有题目了?”笔者请大家放心。微软的员工如果因为应聘者多知道了几道题目,就觉得无法面试,那这个员工还得多磨炼磨炼——也许得再作为应聘者经历几次面试吧 。

也有人会担心:“肯定会有人把答案都背下来,到时候所有人都对答如流,那怎么办?”

如果真的有很多人能够把这几十道题目及答案、几十道扩展问题,以及它们后面的数学、计算机原理、计算机语言及应用都背得滚瓜烂熟,这首先是中国IT行业的好事。其次,这些人都应该来我们公司——不用参加笔试了,直接和我们联系吧!


4.1 金刚坐飞机问题


国外有一条谜语:

问:体重800磅的大猩猩在什么地方坐?

答:它爱在哪儿坐就在哪儿坐。

这条谜语一般用来形容一些“强人”并不遵守大家公认的规则,所以要对其行为保持警惕。

现在有一班飞机将要起飞,乘客们正准备按机票号码(1, 2, 3, …,N)依次排队登机。突然来了一只大猩猩(对,他叫金刚)。他也有飞机票,但是他插队第一个登上了飞机,然后随意地选了一个座位坐下了 。根据社会的和谐程度,其他的乘客有两种反应:

  1. 乘客们都义愤填膺,“既然金刚同志不遵守规定,为什么我要遵守?”他们也随意地找位置坐下,并且坚决不让座给其他乘客。
  2. 乘客们虽然感到愤怒,但还是以“和谐”为重,如果自己的位置没有被占领,就赶紧坐下,如果自己的位置已经被别人(或者金刚同志)占了,就随机地选择另一个位置坐下,并开始闭目养神,不再挪动。

在这两种情况下,第i个乘客(除去金刚同志之外)坐到自己原机票位置的概率分别是多少?

包氏解法(数学归纳法):
(一)先看第一问,我认为作者总结的公式太抽象了,至少能看懂那个公式的人不多。
遇到这样的问题,就是枚举,猜出公式,然后数学归纳法。
假设N=3,即1、2、3。
先来分析第一个人的概率:
如果金刚占了1,概率1/3,那么第1个人永远没机会坐到自己座位,概率为0。
如果金刚不占1(占了2或3)——概率2/3,这种情况下,第1个人可以在1和另一个座位(2或3)中进行选择,概率1/2,即P=2/3 *
1/2 = 1/3。
合计:1/3——这是第一个人坐到自己座位的概率。
再来分析第2个人的概率:
果金刚占了2,概率1/3,那么第2个人永远没机会坐到自己座位,概率为0。
如果金刚不占2(占了1或3),——概率2/3,这种情况下,我们要看第1个人,分2种情况:
第1个人占2的概率为1/2(因为还剩2个位子),那么第2个人永远没机会坐到自己座位,即P=0;
第1个人不占2的概率也是1/2,那么最后一个位子肯定是2,概率为1。则P=2/3*1/2 * 1=1/3
合计:1/3
第3个人的概率就不要算了,因为没有位子了(N+1个人,N个位子,最后一个人肯定没位子)。
综上,我猜测答案为1/N。
其实我心里也没底,于是我让N=4,继续分析,但是这次,概率为0的事件我不再列出来了:
第一个人的概率
如果金刚不占1(占了2、3或4)——概率3/4,这种情况下,第1个人可以在剩下的3个座位中进行选择1,概率1/3,则P=3/4 * 1/3
= 1/4。
合计:1/4——这是第一个人坐到自己座位的概率。
第2个人的概率:
如果金刚不占2(占了1、3或4),——概率3/4,这种情况下,我们要看第1个人在剩下的3个位置中不占2的概率:2/3。接下来第2个人占2的概率是1/2。则P=3/4
  • 2/3 * 1/2 = 1/4
合计:1/4
第3个人的概率:
如果金刚不占3(占了1、2或4),——概率3/4,这种情况下,我们要看第1个人在剩下的3个位置中不占3的概率:2/3。接下来第2个人在剩下的2个位置中不占3的概率是1/2,第3个人只剩下一个3可以选,概率为1。则P=3/4
  • 2/3 * 1/2 * 1= 1/4
合计:1/4
观察得到结论:对于第i个人,我们先计算出金刚、以及第1个人、第2个人……第(i-1)个人——她们不占第i个位置的概率,分别是(N-1)/N、(N-2)/(N-1)、(N-3)/(N-2)直到(N-i)/(N-i+1),然后计算出第i个人在剩余的N-i个位子中占到第i个位子的概率,也就是1/(N-i),把以上这些概率相乘,乘积为1/N,这就是最后的结果。
当然,当i=N的时候,概率永远为0,因为最后一名没有位子选了。
也许我是数学系的,思考角度和科班出身的计算机系mm不太一样。

(二)再看第2问:
话说,长时间以来,我觉得这个答案是错的。
仍然按照刚才的思路进行枚举:
最简单的情况,令N=2,就是说,只有2个元素:1和2。
我们先看i=1的情形,也就是第一个乘客的概率
如果金刚选择1坐下,那么第一个乘客永远没机会,为0。
如果金刚选择2坐下,概率1/2,那么只剩下第一个位置为第一个乘客,P=1/2 * 1 = 1/2。
合计:f(1) = 1/2。
我们再看i=2的情形
还是那句话,最后一个人概率永远为0。
但是,按照作者给出的公式:这两个值分别是f(1)=2/3和f(2) = 1/2。
所以,我猜测,这个公式应该是F(i) = f(i) = (N-i)/(N-i+1)。很奇怪邹欣为什么没写几个TestCase来试试。
心里还是没底,毕竟作者是微软的,于是我分别测试了N=3和N=4情况下,i为2和3的情形。
比如说N=4,i=2
我发现,当金刚占了第1个位置,那么,第1个人不占2的概率是2/3(因为还剩下3个数),此时第2个人肯定可以占2。f(i) = 2/3
比如说N=5,i=3:
当金刚占了第1个位置,那么,接下来分只考虑第一个人不占3的两种情况:
第一个人占2的概率是1/4,那么第2个人不占3的概率是2/3,则第3个人肯定占3。
第1个人不占2也不占3的概率是1/2,此时第2个人肯定占2,第3个人肯定占3。
计:1/4 * 2/3 + 1/2 = 2/3
当金刚占了第2个位置,那么,第一个人肯定占1,第2个人不占3的概率是2/3,此时第3个人肯定可以占3。
合计2/3
将N和i(这里i>n)推而广之:
当金刚占了第n个位置,那么不计第n-1个人以前的乘客,因为他们肯定能做到自己的位置。那么现在,还有第n个乘客,以及剩下的N-n个乘客(从第n+1到第N个)。
于是问题退化为:第n个乘客化身为金刚,剩下的(N-n)个乘客按顺序登机,新的金刚插队第一个登机,随意在第n+1到第N个这(N-n)个位置中坐下……
退化题目所得到的结果F(n)和原题目的结果f(n)是一样的(这里要说清楚,一定要使用数学归纳法)。
所以,我相信,经过若干次退化后,因为n<i<N,所以n会先逼近i,也就是说,这个极限是,金刚占了第i-1个位置,然后第i-1个人不占i的可能性是(N-i)/(N-i+1),这个就是我们要计算的f(i)。
综上所述:f(i) = (N-i)/(N-i+1)。
然后进行计算,得到F(n)=(N-i)/(N-i+1)。这貌似才是正确答案。

但是,仔细观察题目,才发现,猩猩手中也握有一张飞机票,那么分子分母相应都要加1,这样的话,原书给出的答案就是对的了。

- flyinghearts flyinghearts
应该先说明下:N是座位数而不是乘客数(除非满座),并且假设 乘客(包括金刚)的机票号都是连续的。
对问题一,每个人都是随机选择座位,任意一个人坐在指定座位的概率相同,因而第i个乘客坐在其座位的概率是 1/N
对问题二,书上的答案是错误的。

若乘客的机票号 小于 金刚的机票号: (N-i)/(N+1-i)
若乘客的机票号 大于 金刚的机票号: (N+1-i)/(N+2-i)

 最简单的例子:N=2,只有两个座位,
  金刚的机票是1号,乘客的机票是2号: 概率:(N+1-i)/(N+2-i) = 1/2
  金刚的机票是2号,乘客的机票是1号: 概率:(N-i)/(N+1-i) = 1/2

概率和座位总数n有关,与机票总数N无关,除非两者相等。
问题二的概率与金刚的机票号有关。

- matrix67 matrix67
第二个问题有一个比较直观的思路
http://www.matrix67.com/blog/archives/4279,可以参考链接中所附的来源

4.2 瓷砖覆盖地板


某年夏天,位于希格玛大厦四层的微软亚洲研究院对办公楼的天井进行了一次大规模的装修。原来的地板铺有N×M块正方形瓷砖,这些瓷砖都已经破损老化了,需要予以更新。装修工人们在前往商店选购新的瓷砖时,发现商店目前只供应长方形的瓷砖,现在的一块长方形瓷砖相当于原来的两块正方形瓷砖,工人们拿不定主意该买多少了,读者朋友们请帮忙分析一下:能否用1×2的瓷砖去覆盖N×M的地板呢?

- matrix67 matrix67
扩展问题:用多米诺骨牌不能覆盖去掉了(1,1)和(8,8)的8x8棋盘(证明:染色法)
扩展问题:用多米诺骨牌一定能覆盖去掉了两个同色格子的8x8国际象棋棋盘(证明:考虑遍历所有64格子的一个回路)

- uniquestudio uniquestudio4.2《瓷砖覆盖地板》 我觉得就是一道打酱油的题目,建议把下面的扩展问题改为正题,求N*M的地板用1*2的瓷砖铺有多少种铺法?可以使用 状态压缩动规求解

- flyinghearts flyinghearts
《瓷砖覆盖地板》题目的难度和两道扩展题差的可不是一两个级别。个人觉得本书对扩展题的选取,过于看重题目的相似性,这就造成很多扩展题远难于题目,题目讲解用到的方法无法用于扩展题,读者必须自己想新方法解决。
- firewoods firewoods:@flyinghearts
//這個確實有道理, 有些擴展題和原題的難度相差很大, 用到的算法也完全不一樣, 一般對擴展理解還是在原題的基礎上做一些推廣.

4.3 买票找零


在一场激烈的足球赛开始前,售票工作正在紧张地进行中。每张球票为50元。现有2n个人排队购票,其中有n个人手持50元的钞票,另外n个人手持100元的钞票,假设开始售票时售票处没有零钱。问这2n个人有多少种排队方式,不至使售票处出现找不开钱的局面?

- gpww gpww 这个问题可参考卡特兰数(Catalan) 评论里面邹老师还提出过新问题

- flyinghearts flyinghearts
希望增加 catalan数应用的一些例子

- uniquestudio uniquestudio4.3 《买票找零》 卡特兰数问题


4.4 点是否在三角形内



如果在一个二维坐标系中,已知三角形顶点的坐标,那么对于坐标系中的任意一点,如何判断该点是否在三角形内(点在三角形边线上也可)?

假设三角形顶点的坐标为ABC(逆时针顺序),需要判断点D是否在该三角形内。

这个问题比较简单,但是可以通过多种有趣的思路来避免采用复杂的计算方式。

- miloyip miloyip 文中兩個解都不是最優,請參考《Geometric Tools for Computer Graphics》p.695-697

- flyinghearts flyinghearts:题目“假设三角形顶点的坐标为ABC(逆时针顺序)”,对“逆时针顺序”的限制没必要,应该去除。题目最好分2D和3D情况。
2D下,应该用矢量相乘法计算面积,而不应该用海伦公式,事实上,面积法和后面的三矢量同向法是等价的(矢量a b c同向,则 |a+b+c| = |a| + |b| + |c| )。如果是用浮点数表示坐标,由于浮点数取绝对值可以只要一个CPU指令,面积法效率更高。
3D下,应该加入“重力坐标法”。

- uniquestudio uniquestudio4.4 《点是否在三角形内》 简单了点 不过扩展问题很好

- flyinghearts flyinghearts:《点是否在三角形内》看起来很简单,但要做到高效也不是那么容易的,在网上看过的一些文章,要么实现比较低效,要么事先假设四点共面。

4.5 磁带文件存放优化


磁带是一种线性存储设备,一个文件在磁带上的存储区域是完整而且连续的,而多个文件的存储区域是相互独立且连续分布的,如图4-9所示。与今天大量使用的磁盘式存储设备不同,磁带没有扇区、柱面、磁道等概念,所以在进行文件寻址时需要耗费线性时间,即要定位到磁带上的第n个文件,须要依次经过前面的n-1个文件的磁带长度。如今,磁盘式存储设备一般能以低于线性时间的效率进行寻址,但是磁带式存储设备因其低廉的价格,简单的存储结构及海量的存储空间,在今天依然被许多数据中心选为数据备份设备。

_2011-01-19_上午10.45.55.png

大型的数据中心一般会采用一个磁带SAN(Storage Area Network,存储区域网络)作为备份设备(如图4-10所示)。假设其中一盘磁带上有n份文件,它们的长度分别为L[0], L[1], … , L[n-1],且被访问的概率分别为P[0], P[1], …, P[n-1]。请问怎样安排它们在磁带上的存储顺序最好?
_2011-01-19_上午10.47.54.png
- flyinghearts flyinghearts:书中的推导得不出“P[i]/L[i]的值从大到小排列即为最佳存储顺序”这个结论。


4.6 桶中取黑白球


有一个桶,里面有白球、黑球各100个,人们必须按照以下规则把球取出来:

  1. 每次从桶里面拿两个球;
  2. 如果是两个同色的球,就再放入一个黑球;
  3. 如果是两个异色的球,就再放入一个白球。

问:最后桶里面只剩下一个黑球的概率是多少?

- matrix67 matrix67

与奇偶相关的问题有很多扩展。

扩展问题:一场会议上有n个人,某些人之间握过手。求证:握手次数为奇数的人总有偶数个。
证明:把当前握手次数为奇数的人称为“奇数人”,把当前握手次数为偶数的人称为“偶数人”。把握手次数为奇数的人数记作x。两个奇数人握手,x减2;两个偶数人握手,x加2;一个奇数人和一个偶数人握手,x不变。由于初始时x=0,因此x始终为偶数。与原题有异曲同工之妙。
另证:显然,所有人的握手次数总和是偶数(因为每回握手都被算了两次)。因此,握手次数为奇数的人必须有偶数个。

扩展问题:桌上有两个盒子,一个盒子里有 51 枚硬币,一个盒子里有 101 枚硬币。 Alice 和 Bob 轮流把其中一个盒子的硬币倒掉,再把另一个盒子里的硬币分装在两个盒子中。最后谁不能继续操作了,谁就输了。如果 Alice 先走,谁有必胜策略?
答案: Bob 必胜。 Alice 走后,两个盒子里的硬币数必然是一奇一偶。 Bob 倒掉有奇数枚硬币的盒子,把剩下的硬币分成 1 加另一个奇数。这样 Bob 面前总有一个盒子里有偶数枚硬币,因此他始终有走的。

- flyinghearts flyinghearts:
书中的解释有点复杂。从桶中取的两个球的颜色有4种情况:
取出的球 | 放入的球
白 白 | 黑
黑 黑 | 黑
白 黑 | 白
黑 白 | 白
无论哪种情况,黑球数要么增加1,要么减小1, 白球数要么不变,要么减小2。即每次操作后,白球数的“奇偶性”保持不变,因些,
最后剩余的白球数 = 白球的初始个数 % 2。
刚开始有白球100个,因而最后剩下的白球数为0,即最后剩下的球为黑球。

4.7 蚂蚁爬杆


有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过两只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,它们会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最短时间和最长时间,如图4-11所示。
4.11.png
图4-11

- matrix67 matrix67

补充一个有异曲同工之处的算法问题

扩展问题:一场赛跑中,n个人站在n个不同的出发点,以不同的速度匀速向终点奔跑。开始赛跑时,一个摄影师在路中间某个位置骑车摄影,他总是跟着新追上来的人跑,也就是说如果后面有人超过摄影师正在跟踪拍摄的人,他就转而跟着这个新上来的人跑。给定n个人、摄影师和终点在数轴上的位置,给出所有人的速度,求摄影师到达终点的时间。
算法:只需要看初始时位于摄影师后面的人里谁最先到达终点。

补充一个有异曲同工之处的行程问题

扩展问题:小 A 站在甲、乙两地之间的某个位置,他想乘坐出租车到乙地去。他看见一辆空车远远地从甲地驶来,而此时整条路上并没有别人与他争抢空车。我们假定车的行驶速度和人的步行速度都是固定不变的,并且车速大于人速。为了更快地到达目的地,小 A 应该怎样做呢?你认为下面哪种思路是正确的?
(A) 由于车速大于人速,小 A 应该尽可能早地上车,充分利用汽车的速度优势。因此,小 A 应该迎着空车走上去,提前与车相遇。
(B) 为了尽早到达目的地,小 A 应该充分利用时间,马不停蹄地赶往目的地。因此,他应该自己先朝目的地走一段路,再让出租车载他走完剩下的路程。
答案:两种方案花费的时间是一样的。只要站在出租车的角度上想一想,问题就变得很显然了:不管小 A 在哪儿上车,出租车都要驶完甲地到乙地的全部路程,因此小 A 到达乙地的时间总等于出租车驶完全程的时间,加上途中接小 A 上车可能耽误的时间。

4.8 三角形测试用例



前来面试研发职位的同学大部分都觉得“测试”是一个很容易的事情,但是事实并非如此。测试和开发还是有些不一样的。打个比方,看到一杯半满的水,从乐观的角度看,会觉得——杯子一半都满了!而从悲观的角度来看——杯子还有一半是空的!测试工程师必须具备从各种角度看问题,找出可能缺陷的能力。当团队中别的同事欢呼“项目快要完成了”的时候,测试工程师必须能看到杯子里还有什么地方是空的。

我们举一个判定三角形的例子:输入三角形的三条边长,判断是否能构成一个三角形(不考虑退化三角形,即面积为零的三角形),是什么样的三角形(直角、锐角、钝角、等边、等腰)。

函数声明为:byte GetTriangleType(int, int, int)。

  1. 如何用一个byte来表示各种输出情况?
  2. 如果你是一名测试工程师,应该如何写测试用例来完成功能测试呢?
- MichaelPeng MichaelPeng: 这里作为边界条件还可以加上三角形两条短边的平方和或者最长边平方大于等于最大整数的情形

4.9 数独知多少



通过前面题目(1.15节“构造数独”)的介绍,相信大家都已经很熟悉数独游戏了,我们还有几个“小”问题没有解决。

图4-13是一个已完成的数独,可以看出,图中每一行、每一列和九个3×3的小矩阵都没有重复的数字出现。

_2011-01-19_上午11.14.12.png

问题

一共有多少种不同的数独解答呢?其中有多少种是独立的解答呢?

如果我们要用一个简单的字符串来表示各种数独(例如:上面的数独可以用“125864…685219”来表示),如何在保证一一对应的基础上,让字符串的长度最短?


4.10 数字哑谜和回文


人越大越聪明还是越大越笨?最近笔者看了一些小学低年级的“奥数”题目,把脑袋拍痛了,还做不出来,真想列几个二元一次方程,把解求出来——不过小学低年级还没有学方程,所以这个不算;笔者也想干脆写个程序,用蛮力搜索的方法,把答案找出来算了,这个肯定也不是正确的解法。看来我们“大人”依赖于“方程”、“程序”太多了,脑子变得不灵活了。

下面的问题,可以用小学三年级的方法解决,也可以用初中列方程式的办法解决,还可以用大学的高级编程语言解决。读者有没有兴趣尝试和比较一下各种解法?

1. 神奇的9位数。能不能找出符合如下条件的9位数:
这个数包括了1 ~ 9这9个数字;
这个9位数的前n位都能被n整除,若这个数表示为abcdefghi,则ab可以被2整除,abc可以被3整除……abcdefghi 可以被9整除。
2. 有这样一个乘法算式:
人过大佛寺*我=寺佛大过人

这里面每一字都代表着一个数字,并且不同的字代表的数字不同,你能把这些数字都找出来么?

- tintalk tintalk Section 4.10, Page #308, 扩展问题1的简介, 可添加对逆行卡农的介绍:
回文在作曲中也有应用,称为“逆行卡农”或“蟹行卡农”(Crab Canon),主句各音出现次序颠倒,其中较著名的一段出现在巴赫的《音乐的奉献》中 ( J.S.Bach, BWV 1079, The Musical Offering).

- matrix67 matrix67 补充一些数字谜的例子。

数字谜的精彩之处在于,它有唯一解。所以说我非常喜欢381654729这个谜题。有一个类似的谜题:

扩展问题:用1到9组成一个九位数,使得每相邻两个数字组成的两位数正好都是两个一位数的乘积。
答案:728163549(唯一解!)

附一些我喜欢的经典数字谜,规则都相同:相同字母代表相同的数字,不同字母代表不同的数字。并且,它们都是唯一解!

扩展问题:SEND + MORE = MONEY
扩展问题:√(PASSION) = KISS
扩展问题:THREE + THREE + TWO + TWO + ONE = ELEVEN

最后这个数字谜叫做Doubly-True Alphametic,编程寻找这样的数字谜本身又是一个难题。可以证明上面这个Doubly-True Alphametic是合法的Alphametic中得数“最小的”一个。
寻找汉字的Doubly-True Alphametic也是一件很有乐趣的事情。我曾经找到一个:

扩展问题:二十一 + 九十九 = 一百二十
扩展问题:寻找更多类似的谜题

参见:http://www.matrix67.com/blog/archives/2856

汉字数字谜其实也有不少。一个经典的谜题是:

扩展问题:√(轻轻的)=√(我)+走了,正-如 / 我=√(轻轻的) / √来

4.11 扫雷游戏的概率


让我们再回到扫雷(Minesweeper)游戏,游戏开始时用户的第一次点击并不会碰到任何地雷,程序在此之后才开始随机放置地雷。第二次点击的时候就要小心了,可能一下就“遇雷身亡”了。

我们看一个例子,在16×16的地雷阵中,有40个地雷。用户点击了两下,出现如图4-22的局面。我们分析图中的这一个局部(如图4-23所示)。

_2011-01-19_上午11.21.39.png

问题1:当这个游戏有40个地雷没有被发现的时候,A、B、C三个方块有地雷的概率(P(A), P(B), P(C))各是多少?

问题2:这个游戏局面一共有16×16 = 256个方块,P(A)、P(B)、P(C)的相互大小关系和当前局面中地雷的总数有联系么?比如,当地雷总数从10个逐渐变化到240个,P(A)、P(B)和P(C)的三条曲线是如何变化的 ?它们会不会相交?