解答Google的一道面试题

http://blog.csdn.net/jiaomeng/archive/2006/12/08/1435226.aspx

这几天有一道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/x²，令f’(x)=0求出驻点x=10(x=-10舍去)。由于f(x)存在最小值且只有一个驻点，所以当x=10时f(x)取得最小值，最小值为18。这样就解答了这个问题。

 

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