By

文章目錄

扔蛋问题说的是，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时，测试层数也可以类似的求解

打赏作者

文章目錄