文章目錄

扔蛋问题说的是,100层楼,给两个特制鸡蛋。从某层扔下鸡蛋,鸡蛋就会碎。问至少要测试多少次才能试出这个层数。对于这个问题,许多人都可以背出答案14层。但如果是200层呢?

事实上,还可以对这题进行扩展,假设n层,e个鸡蛋,求至少要测试多少次,才能测出这个层数。

对于这题,可以用动态规划。还是在面4399时,面试官要我解释什么是动态规划,当时没能解释清楚。现在想来,动态规划有两个重要的因素,一个是最优子结构,还有一个是重叠子问题。按我的理解,最优子结构说的是,当前的最优解包含了子问题的最优解。重叠子问题说的是,子问题具有重叠部分。

而对于这题,可以写出一个递推公式,设n为楼层数,e为鸡蛋数。
f(n,e) = 1 + min{max{f(n - r, e),f(r - 1, e -1)}} 其中r属于{2,3,…,n - 1},初始条件为f(n,1) = n, f(1,e) = 1, f(2,e) = 2. 这里要求n,e都是正整数。
写成程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def egg(n, e=2):
dp = [[n for i in xrange(e + 1)] for j in xrange(n + 1)]
for i in xrange(1, n + 1):
dp[i][1] = i
for i in xrange(1, e + 1):
dp[1][i] = 1
dp[2][i] = 2
for i in xrange(3, n + 1):
for j in xrange(2, e + 1):
for r in xrange(1, n):
dp[i][j] = min(dp[i][j], 1 + max(dp[i - r][j], dp[r - 1][j - 1]))

return dp[n][e]

print egg(100, 2)

对于鸡蛋数为2时,还有特殊的解法。在鸡蛋数为2时,楼层数与测试次数如下:
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5

于是可以猜测,对于楼层数n ,只要找到第一个x ,使得 x * (x + 1) / 2 >= n即可,对于100,正好是14。类似地,对于开头提出的鸡蛋数为2,楼层数为200时,测试层数也可以类似的求解

文章目錄