2006年Google面试题：确定临界楼层

问题：

有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。

来自焦萌的分析：

为了得到两个棋子的最优策略，我们先简化问题，看看一个棋子的情况。如果手中只有一个棋子，为了得知临界层面，你只有一种选择：从2楼开始，一层一层地试，直到棋子被打碎，此时你站的楼层就是所求的临界层面。在最差的情况下，我们需要投掷99-2+1=98次，你可能奇怪为什么不是100-2+1=99次，那是因为题目已经告诉我们“从这个大厦的某一层扔下围棋子就会碎”，所以在99层扔下来还没碎的话就不用去100层了——从那里扔它一定会碎。

从一个棋子的策略我们可以看出，一个棋子就足以解答这个问题了。现在又多了一个棋子，该如何利用它呢？很自然地，我们希望能通过这个棋子缩小这种一层一层查找的范围。为了缩小范围，我们将整个大厦的层数分成x段，在这x段中查找那个临界段，然后在临界段中再一层一层地找临界层。比如可以将大楼分成4段，我们分别在25层、50层、75层投掷棋子，以确定临界段；如果临界段在25层到50层，我们再从26层开始一层一层查找临界层。

分析到这里，问题就转化成了如何确定分段数x使棋子投掷的次数最少的问题。在最差的情况下，要确定临界段，我们需要投掷100/x-1次；确定了临界段之后要确定临界层，我们需要再投掷x-1次。因此，问题就成了求函数f(x)=(100/x-1)+(x-1)的最小值问题。先对f(x)求导，f’(x)=1-100/x2，令f’(x)=0求出驻点x=10(x=-10舍去)。由于f(x)存在最小值且只有一个驻点，所以当x=10时f(x)取得最小值，最小值为18。这样就解答了这个问题。

其实10这个结果也很容易直接看出来。在只有一个棋子时，我们相当于把整个大厦分成了一段，这一段有100层。在有两个棋子时，我们有很多分法，但无论怎么分，如果分成k1段，每段有k2层，那么就有k1k2=100。在最坏的情况下，我们需要投掷(k1-1)+(k2-1)次。因此问题也可以表述成在k1k2=100的条件约束下，如何让函数f(k1,k2)= k1+k2最小。在初等数学中，我们知道在矩形面积一定的情况下，正方形的周长最小。利用这个结论，我们可以直接得出结论k1=k2=10。

现在问题已经完满解决，但我还想把这个问题扩展一下，把它变成“m层楼n个棋子”的情况。首先来看这样一个问题，给定m层楼，多少个棋子就“足够”了，也就是说，再多的棋子也不能加快查找的过程。在我所能想到的方法里，二分法应该是最优的，如果按二分法来查找，则需要ceiling(log2m)个棋子（ceiling是向上取整函数），超过这个数再多的棋子也无益。

如果n>=ceiling(log2m)，那就采用二分法，现在考虑n< ceiling(log2m)的情况。前面已经看到，当n=2时，问题可以表述成在k1k2=100的条件约束下，求函数f(k1,k2)= k1+k2的最小值。类似地，在n个棋子的情况下，问题可以表述成在k1k2…kn=m的条件约束下，求函数f(k1,k2,…,kn)=k1+k2+…+kn的最小值。利用拉格朗日乘数法，我们可以很容易地求出：当k1=k2=…=kn=n√m时，这个多元函数取得最值。n√m有可能不是整数，因此这只是一个理论上的结果。

我们换一个思路考虑，m层楼n个棋子的问题其实就是如何将m分解成n个因子相乘，从而让各个因子之和最小。如何分解m使得策略最优就成了问题的关键。前面得出的结论提示我们尽量让各个因子相等或者相差较小，它们相加的结果才会较小。比如，100层楼3个棋子的情况，5，5，4应该是一个最优的选择。

考虑到这里，又有一个问题出现了：是不是将m分解的越多越好呢？比如，将100分解成10，10好呢，还是2，5，10好？这个问题其实就是在问，两个大于1的整数，它们的和大呢还是积大。很明显，当然是积大，因此将m分解的越多越好。

数论告诉我们，质数是整数的基础，所有整数都可以分解成若干个质数的乘积。因此，如果将上面的方法发挥到极致，那就要求我们把m分解成质数的乘积。当然，如果棋子足够多，这并不是最优的方法，对质数层楼的段，你仍然可以采用二分法。

来自kingkingxy的分析：

最多14次。从14层开始扔第一次，如果碎了，那么从第2层开始扔，一层层加，直到13层。一共14次。如果没有碎。27层再扔一次。依次推理，从15层到26层一共12次。加上前面的14层，27层2次所以说也是14次。依次这样扔 14 14+13=27 27+12=39 39+11=50 50+10=60 60+9=69 69+8=77 77+7=84 84+6=90 90+5=95 96 97 98 99

最多14次

1+2+3=6 （6+1）=7 如果是扔3次，最多能扔到7楼 1+2+3+4=10（10+1）=11 如果是扔4次，最多能扔到11楼 ... 1+2+3+4+..+14=105 （105+1）=106 如果扔14次最多能扔到 106 楼。

如果200楼的话，按照这种方法。应该需要扔20次

来自阿丹的分析：

假设n为棋子数，i为可以扔的次数，F（n，i）表示可以确保能得到临界点的最大楼层数。

要求n个棋子，楼层为f的情况下的最优解，首先找到i使得F（n，i-1） <f并且F（n，i）> =f。 i即至少需要扔i次才能确保找到临界点。第一次扔的楼层为F（n-1，i-1）+1，以此类推根据第一次扔的结果确定第二次扔的楼层。

对于google的这道题，首先要找到i使得F（2，i-1） <100并且F（2，i）> =100。 F（2，2）= 3 F（2，3）= 3+2+1 =6 F（2，4）= 6+3+1 =10 F（2，5）= 10+4+1 =15 可以发现F（2，n）正好等于1到n的和。 F（2，13）= 91 F（2，14）= 105 得到i = 14，至少需要14次可以确定临界点。至于要得到所有情况下扔的次数最少的最优解，应该不止一种。

补充两句：

把问题还原一下吧。

Google是做搜索引擎的，对海量数据的检索实时性要求很高，因此如果设计一个算法是2层嵌套的话，外层嵌套应该为内层循环做出牺牲。但是这个牺牲不是不计代价的，应该做到总体利益的最大化。其次，外层循环应该为内层循环扫除障碍，缩小内层循环的压力。

n等分查找法，内外层分担的风险都是1/n，外层循环壮烈的时机对内层循环没有实质的影响。但是有种可能，第一个球n次下来都没有坏掉，但是内层循环的压力却一直保持1/n。

递减查找法，内层循环作为外层循环的接班人，外层一旦壮烈内层马上上阵。同样存在外层一直不死的情况，但是内层的压力确是一直在减小的。

讨论地址：http://topic.csdn.net/t/20061206/10/5209914.html

本文地址：/Other/2011/04/06/2006-google-interview-determine-critical-floor