鸡蛋掉落：100层楼2蛋最少试几次

题目

有 100 层楼，某层（含）以上扔鸡蛋会碎、以下不会。你只有 2 个鸡蛋，想找出这个临界层。策略要保证在最坏情况下测试次数最少。最少需要几次？

答案与解析

14 次。 思路是让“最坏情况”的步数恒定：

第一个蛋用来“粗定位”，每次跳一个递减的间隔；碎了之后用第二个蛋在上一落点和这一落点之间逐层细试。若从第 14 层起跳，间隔 14,13,12,…,1，则覆盖 $14+13+\cdots+1=105\ge100$ 层。

最坏情形：第一个蛋在第 14 层没碎、第 27 碎了，则第二个蛋在 15–26 之间最多试 12 次，加上前面 2 次，共 14 次；其它情况也都是 14 次封顶。

一般地，对 $k$ 个蛋、$n$ 层，最少次数由递推 $f(k,e)$ 给出（动态规划），而 $k=2$ 时就是找最小的 $m$ 使 $\frac{m(m+1)}{2}\ge n$。

背后的数学

这是算法面试的常青题鸡蛋掉落（Egg Dropping），核心是最坏情况最小化（minimax）与动态规划。它揭示了“用昂贵资源（会碎的蛋）做大跨度探测、用廉价资源做线性回填”的通用策略，与计算机里“二分探测+线性探测”的权衡异曲同工。