经典面试题23 - 扔鸡蛋的技巧
问题
有一栋100层的高楼，一个鸡蛋从第N层及以上的楼层落下来会摔破， 在第N层以下的楼层落下不会摔破。给你2个鸡蛋，设计方案找出N，并且保证在最坏情况下， 最小化鸡蛋下落的次数。（假设每次摔落时，如果没有摔碎，则不会给鸡蛋带来损耗）
解答
这完全是一道智力题，和所谓的编程算法无关，不要走进二分法的陷阱，归纳法才是争取选择。
首先假设在最坏情况下，鸡蛋下落次数为x，我们为了找出N，一共用鸡蛋做了x次的实验。
那么，我们第一次应该在哪层楼扔鸡蛋呢？
先让我们假设第一次在第y层楼扔的鸡蛋， 如果第一个鸡蛋在第一次扔就碎了，我们就只剩下一个鸡蛋，要用它准确地找出N， 只能从第一层向上，一层一层的往上测试，直到它摔坏为止，这时候答案就出来了。
由于第一个鸡蛋在第y层就摔破了， 所以最坏的情况是第二个鸡蛋要把第1到第y-1层的楼都测试一遍，最后得出结果：
原来鸡蛋在第y-1层才能摔破， 或是在第y-1层仍没摔破，答案就是第y层。
这样一来测试次数是1+(y-1)=x，即第一次测试要在第x层。
如果第一次测试鸡蛋没摔破呢，那N肯定要比x大，要继续往上找，需要在哪一层扔呢？
我们模仿前面的操作，如果第一个鸡蛋在第二次测试中摔破了， 那么第二个鸡蛋的测试次数就只剩下x-2次了(鸡蛋总共下落次数为x，而第一个鸡蛋已经用了2次)。
这样一来，第二次扔鸡蛋的楼层和第一次扔鸡蛋的楼层之间就隔着x-2层。
我们再回过头来看一看：
第一次扔鸡蛋的楼层在第x层，第1层到第x层间共x层；
第1次扔鸡蛋的楼层到第2次扔鸡蛋的楼层间共有x-1层；
同理继续往下，我们可以得出，
第2次扔鸡蛋的楼层到第3次扔鸡蛋的楼层间共有x-2层；
第3次扔鸡蛋的楼层到第4次扔鸡蛋的楼层间共有x-3层；
……
最后把这些互不包含的区间数加起来，应该大于等于总共的楼层数量100，公式如下：
x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100
解方程可知 x = 14。
即先用第1个鸡蛋在以下序列表示的楼层数不断地向上测试，直到它摔破。 再用第2个鸡蛋从上一个没摔破的序列数的下一层开始，向上测试， 即可保证在最坏情况下也只需要测试14次，就能用2个鸡蛋找出从哪一层开始， 往下扔鸡蛋，鸡蛋就会摔破。
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
比如，我第1个鸡蛋是在第69层摔破的，那么我第2个鸡蛋就从第61层开始，向上测试， 第二个鸡蛋最多只需要测试8次(61,62,63,64,65,66, 67,68)，加上第1个鸡蛋测试的 6次(14,27,39,50,60,69)，最坏情况只需要测试14次。
更多
获取更多内容请关注微信公众号豆志昂扬:
- 直接添加公众号豆志昂扬；
- 微信扫描下图二维码；
