智力题——高空抛鸡蛋

Source: Dev.to

来源

高通面试题

题目

有一栋 100 层的楼，和 2 个坚硬的鸡蛋。从楼上扔下鸡蛋，鸡蛋会在大于某一层刚好开始碎。
在最坏情况下，最少要扔多少次，才能一定找出这个临界楼层？

错误思路

二分法：100 → 50 → 25 → 12 → 6 → 3 → 1
这种方法在不同的临界楼层下，扔的次数并不相同，最多可达 50 次（实际可以更少）。

例如，若临界楼层为 49，第一颗鸡蛋在第 50 层碎，随后第二颗鸡蛋只能从第 1 层起逐层向上寻找，直到第 49 层。

正确思路

1. 理解题目

• 无论临界楼层在第几层，都要保证在最坏情况下的最大投掷次数最小。
• 两个鸡蛋的作用：第一颗鸡蛋用于分段，第二颗鸡蛋用于在该段内逐层扫描。

2. 思路核心

在最坏情况下，第一颗鸡蛋的每一次投掷所剩的可扫描层数 + 已经投掷的次数 应保持不变。这样，无论临界层在何处，总投掷次数大致相同。

3. 具体做法

1. 第一次投掷第一颗鸡蛋在第 14 层。
   • 若碎，则第二颗鸡蛋逐层向下扫描，最坏需要 14 次。
   • 若未碎，则第二次投掷第一颗鸡蛋在第 27 层（14 + 13），此时剩余可扫描层数递减为 13。
2. 之后每次递减的层数依次为 12、11、…、1。
3. 这样，无论临界楼层在哪一层，最坏情况下的总投掷次数都是 14 次。

4. 如何确定首层 14

需要满足层数递减的和覆盖 100 层：

$$ 1 + 2 + 3 + \dots + n \ge 100 $$

求最小的整数 (n)，得到 (n = 14)。

---

因此，使用上述递减步长的策略，最坏情况下只需 14 次 投掷即可确定临界楼层。