一幢 200 层的大楼,给你两个鸡蛋。如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,都不碎。这两只鸡蛋一模一样,不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎?

谷歌面试题,前两年用它K了许多成名人物。提出一个策略, 保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少
关注者
617
被浏览
127454

34 个回答

看到靠谱的答案都沉了, 就发了篇文章在blog上:Problem of Two Eggs . 主要内容粘过来, 公式格式懒得转了.

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

搞清楚这题的意思:
第一个鸡蛋用来试探, 只要它从 k 层楼扔下去没碎, 则目标就在[k+1, 200]之间了.
但一旦运气不好碎了, 对于已知的区间, 我们只能用剩下一个鸡蛋从小到大一层层试,
因为我们要保证策略必须成功, 不能冒险了.

"最坏情况下代价最小"这句话十分重要, 它反映了题目的重要数学结构:
我们可以把任何一种策略都看成一个决策树,
每一次扔瓶子都会有两个子节点, 对应碎与不碎的情况下下一步应该扔的楼层.
那么, 策略的一次执行, 是树中的一条从根往下走的路,
当且仅当这条路上出现过形如 k 没碎 与 k+1 碎了的一对节点时, 路停止, 当前节点不再扩展.
那么要找的是这么一棵树, 使得所有路里最长者尽量短, 也即, 要找一个最矮的决策树.

再看一个节点处, 选择楼层时会发生什么.
容易看出, 选择的楼层如果变高, 那么"碎子树"高度不减, "不碎子树"高度不增.
同样的, 选择的楼层变矮的话, "碎子树"高度不增, "不碎子树"高度不减.

这时候答案很明显了: 为了使两子树中高度最大者尽量小, 我们的选择应当使两子树高度尽量接近.
最终希望的结果是, 整个二叉树尽量像一个满二叉树.

假设第一次在根节点上, 我们选择扔k层, 其"碎子树"的高度显然是k - 1.
为了考虑不碎子树的高度, 设不碎后第二次扔m层(显然m > k ),
则这个新节点的碎子树高度为 m - k - 1, 不碎子树高度仍然未知,
但按照满二叉树的目标, 我们认为它与碎子树相同或少1就好.
那么在根节点上的不碎子树的高度就是m -k-1 + 1, 令它与碎子树高度相同, 于是:
m - k - 1 + 1 = k - 1 => m = k + k - 1

也即, 如果第一次扔在k层, 第二次应该高k-1 层, 这可以有直观一点的理解:
每扔一次, 就要更保守一些, 所以让区间长度少1. [1, k) -> [k + 1, 2k - 1).
用类似刚才的分析, 可以继续得到, 下一次应该增高k - 2, 再下一次应该增高k - 3.

如果大楼100层, 考虑:
k + (k-1) + \cdots + 1 = \frac{k(k+1)}{2} = 100 \Rightarrow k \approx 14

所以第一次扔14层, 最坏需要14次(策略不唯一, 树的叶子可以交换位置).200层的话, 类似得到k =20.

以上是数学做法...当然还有代码做法....
设f(n, m)为n层楼, m个蛋所需次数, 那么它成了一道DP题..
\begin{eqnarray}
f(0, m) & = & 0, (m >= 1)\\
f(n, 1) & = & n, (n >= 1)\\
f(n, m) & = & \min_{1 \le i \le n} \{ \max\{ f(i - 1, m - 1), f(n - i, m)\}\} + 1 \\
\end{eqnarray}

以下代码python3 only:
import functools
@functools.lru_cache(maxsize=None)
def f(n, m):
    if n == 0:
        return 0
    if m == 1:
        return n

    ans = min([max([f(i - 1, m - 1), f(n - i, m)]) for i in range(1, n + 1)]) + 1
    return ans

print(f(100, 2))	# 14
print(f(200, 2))	# 20
步进20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5
最坏结果是20次
为什么?