扔鸡蛋问题解析

上周看到一篇文章，描述的是 Google 的经典面试题目“扔鸡蛋”，题目如下。

你站在一栋 100 层高的大楼里，手中有 2 个完全相同的鸡蛋。有一未知的临界楼层，鸡蛋从临界楼层以下扔下去，一定不会碎；从临界楼层以上丢下去，一定会碎。已知未碎的鸡蛋可以重复使用，碎了的鸡蛋就不能再往下扔了。要求即便在最坏情况下，尝试次数也要尽可能少。请问最少需要尝试多少次能够找到这个临界楼层？

这道题目目前应该有很多解答的文章和思路，下面就简单聊下我的解答思路，如果对你有帮助那最好不过了。

# 从一枚鸡蛋开始思考

首先我们先梳理下，如果我们只有 1 枚鸡蛋的时候需要如何做。是不是只能从第一层开始逐层向上尝试？最坏情况需要尝试 100 次。我们别无他法，因为没有试错的机会。

但是如果有两枚鸡蛋，则我们可以用一枚鸡蛋来定位位置，用剩下的鸡蛋去尝试，也就是说多了一次试错的机会。

# 为什么二分法不行？

可能你会突然想到二分法，这是一个非常优秀的思想，不过很遗憾这里不能用。假设我们用二分法，第一次在 50 层，临界楼层在 100 层，那我们需要从 51 开始尝试到 100。

其次可能还会有按照 10、20、30……这样楼层来划分的方式，当然也可以，不过会存在一个最极端情况：临界楼层是 99 层。我们需要尝试 10、20……直到 100，一共 10 次，之后从 91 开始到 99，一共需要 9 步，加上之前的 10 步，总共 19 次。这个问题在于，如果层数足够大，那么需要的尝试次数就会被拉长。

# 转变思路：固定尝试次数

现在需要转变一下思路。我们先模拟一下，假设第一步扔到 5 层，如果碎了，说明临界楼层在 1–4 层，结束。

假设没有碎，那我们需要继续扔一次。假设第二次扔到 10 层时碎了，我们需要从 6–9 层开始查找。

假设扔到 15 层时碎了，我们需要从 11–14 层查找。

我们来计算一下扔的楼层和步数：

• 第一次：5 层，需要从 1–4 层查找，共计查找 4 次。
• 第二次：10 层，需要从 6–9 层查找，共计查找 4 次。
• 第三次：15 层，需要从 11–14 层查找，共计查找 4 次。

上面有一个隐藏的成本：我们从 5 层往 10 层扔的时候，5 层已经用过一次了；第三次扔 15 层时，前两次的扔鸡蛋次数也已经计入成本。

假设我们希望扔的次数是固定的，以确保查找未知楼层的步骤不会根据楼层不同而抖动。我们将其设为 $x$，$x$ 代表最大查找次数。

我们来推理一下：

1. 如果扔鸡蛋后鸡蛋碎裂，说明我们的鸡蛋数量减少 1，然后需要在扔的楼层之下的楼层中继续查找，剩余最多 $x-1$ 次尝试。
2. 如果没有破碎，则剩余尝试次数为 $x-1$。

这个公式可以概括为：

$$x + (x-1) + (x-2) + \cdots + 1$$

这里我说明一下：$x-1$ 可以很好理解，就是扔的楼层下方的查找范围；后续的 $x-2$、$x-3$……都是因为之前的步骤已经消耗了查找次数，所以要减少 1。

# 举例验证

例如我们代入一下，假设最大查找次数为 5 次：

• 第一次，扔 5 层，然后从 1–4 层查找，共 5 次。
• 第二次，因为已经消耗了一次，所以只能扔 4 层，即扔到 9 层，然后从 6–8 层查找，加上之前扔的一次刚好 5 次。
• 第三次，之前消耗两次，所以扔 3 层，即扔到 12 层，然后从 10–11 层查找。
• 第四次，之前消耗三次，所以扔 2 层，即扔到 14 层，然后从 13 层查找。
• 第五次，之前消耗四次，所以只能扔 1 次，即第 15 层。

$$5 + 4 + 3 + 2 + 1 = 15 \text{ 层}$$

所以只能查找到 15 层，当 $x = 5$ 时。

# 公式推导与求解

好，我们现在已经理解上面的公式了。我们变形一下，代入高斯求和公式。在此之前回顾一下高斯如何计算 $1 + 2 + 3 + \cdots + 100$：

$$\frac{(1 + 100) \times 100}{2} = 5050$$

对于我们的问题，求和公式为：

$$x + (x-1) + \cdots + 1 = \frac{(x + 1) \times x}{2}$$

我们只要确保计算结果 $\geq 100$，就可以求解出最小的 $x$。

试算几个值：

• $x = 10$：$\frac{11 \times 10}{2} = 55$
• $x = 15$：$\frac{16 \times 15}{2} = 120$，这超出了
• $x = 14$：$\frac{15 \times 14}{2} = 105$，这超出一点
• $x = 13$：$\frac{14 \times 13}{2} = 91$，这不够

所以得出结论：至少需要 14 步才能找到临界楼层。

# TypeScript 函数实现

下面是用 TypeScript 编写的计算函数：

/**
 * 计算最坏情况下找到临界楼层所需的最少尝试次数
 * @param floors 总楼层数
 * @returns 最少尝试次数
 */
function minEggDropAttempts(floors: number): number {
  let x = 1;
  while ((x * (x + 1)) / 2 < floors) {
    x++;
  }
  return x;
}

// 对于 100 层楼，结果为 14
console.log(minEggDropAttempts(100)); // 14