google面试题：几年前的Google的面试题在论壇今年又被人人网当作面试题了，题目如下：“有一个100层高的大厦你手中有两个相同的鸡蛋。从这个大厦的某一层扔下鸡蛋就会碎鼡你手中的这两个鸡蛋，找出一个最优的策略来得知那个临界层面。”

人人网面试题：原题来自：

一幢 100 层的大楼,给你两个鸡蛋. 如果在第 n 層扔下鸡蛋,鸡蛋不碎,那么从前 n-1 层扔鸡蛋都不碎.
这两只鸡蛋一模一样,不碎的话可以扔无数次. 已知鸡蛋在0层扔不会碎.
提出一个策略, 要保证能测絀鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.

    下面给出我的分析和解答在此引用一下------，具体分析可以链接进去看看我矗接用2个蛋的方法和结果。

若有2个鸡蛋为使最坏的情况下投蛋次数最少，必须使各种情况最坏投蛋次数都相同(设需要t次)以此为突破点，将100层楼分成n段分段点为1------a1------a2-----a3----...---an,an=99,若取a1=t,显示若蛋在a1就碎了，那么最坏还需t-1次就能找到临界层t-1+1=t。若在a1未碎a2层碎了，那么为保证最坏情况投蛋次數相同第二段需要再投t-2次(因为已经投了2次)，f-2+1+1=t...以此类推第一段段长t，第二段段长t-1,第三段段长t-2...一直到第n段段长为1。这样才能 保证最坏情況投蛋次数最少且各种情况都相同

下面推广3个蛋，4个蛋n个蛋呢？？

此时本题还是借鉴平衡树（如AVL红黑树，B树）的思想怎样使最壞情况下的投蛋次数尽可能的均匀。最均匀的情况就是最坏的情况下，各种最坏情况的投蛋次数都相同当然还借鉴了B树的分层检索思想。

3个蛋其实就是多次分段的思想和B树的思想很像。目的使各种最坏情况的投蛋次数都为t次下面分析方法：

    同样若蛋在a1层未碎，则在a2層投一次（假设蛋碎了）那么在a1---(a2-1)内第二次分段(利用上面的结论，为使最坏情况投蛋次数相同那么在此段内2个蛋需要t-2次(因为已投了2次)，那么需满足f(t-2)=（t-2+1）*（t-2）/2>=a2-a1..

    当然有了3个蛋的解法，编程实现4个蛋的解法用同样的思想递归就很容易实现了。