鸡蛋下落问题

面试的时候被问到了。。

Question

两个鸡蛋从 100 层高的楼往下丢,最少要扔几次鸡蛋才能算出那一层是鸡蛋的临界层?

Intuition

Mathematic

  • 第一个鸡蛋从 k 楼下落,如果碎了,那就必须 [1, k - 1] 层试了,然后最坏就是 k 次
  • 如果没碎,那就是从 [k + 1, 100] 找一个楼层开始试,

那如果没碎,下一次的楼层如何选择。可以把问题看成一个决策树的样子,要尝试去构造一个满二叉树。

假设第一次在根节点上, 我们选择扔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 层。

$$k + (k - 1) + … + 1 = \frac{k(k+1)}{2} = 100 \Rightarrow k \approx 14$$

Dynamic Programming

用 f(n, m) 表示所需最少次数,n 表示楼层高度,m 表示蛋的个数。

  • $f(0,m)=0, m>=1$
  • $f(n,1)=n, n>=1$

$$f(n,m)=\min_{1\leq i \leq n}\{\max\{f(i-1,m-1), f(n-i,m)\}\} + 1$$

这就是状态转移方程了。

1
2
3
4
5
6
7
8
9
10
11
12
13
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

References