首页 > 剑指offer > 扔鸡蛋问题(Egg Dropping Puzzle)
2014
04-07

扔鸡蛋问题(Egg Dropping Puzzle)

据说这是一道google的面试题. 看似是一个智力题,实际是编程题。

两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。现有座36层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置,可以摔碎两个鸡蛋,要求用最少的测试次数。

如果你从某一层楼扔下鸡蛋,它没有碎,则这个鸡蛋你可以继续用
如果这个鸡蛋摔碎了,则你可以用来测试的鸡蛋减少一个
所有鸡蛋的质量相同(都会在同一楼层以上摔碎)
对于一个鸡蛋,如果其在楼层i扔下的时候摔碎了,对于任何不小于i的楼层,这个鸡蛋都会被摔碎
如果在楼层i扔下的时候没有摔碎,则对于任何不大于i的楼层,这颗鸡蛋也不会摔碎
从第1层扔下,鸡蛋不一定完好,从第36层扔下,鸡蛋也不一定会摔碎。

实际上,我们的终极目的是要找出连续的两层楼i,i+1。在楼层i鸡蛋没有摔碎,在楼层i+1鸡蛋碎了,问题的关键之处在于,测试之前,你并不知道鸡蛋会在哪一层摔碎,你需要找到的是一种测试方案,这种测试方案,无论鸡蛋会在哪层被摔碎,都至多只需要m次测试,在所有这些测试方案中,m的值最小。

为什么是两个鸡蛋呢?如果只有一个鸡蛋,我们只能从下往上一层一层的测试。对于2个鸡蛋,比较容易想到的就是使用二分的方法,现在18层测试,如果这颗碎了,则你从第1层,到第17层,依次用第2颗鸡蛋测试。否则继续用两个鸡蛋测试上半部分的楼层,最多需要18次测试,减少了一半。看似是个不错的方法,可惜正确答案是8次。

其实,对于任何连续的M层,这M层在下面或在下面,对于这M层来说需要的测试次数都没有影响。因此,可以把这个问题一般化,考虑n个鸡蛋 k层楼,记为E(n,k)。解决的办法是试着从每一层掉落一个鸡蛋(从1到k)并递归计算需要在最坏的情况下需要的最小测试次数。考虑用程序来穷举所有情况找到答案。

1) 最优子结构

当我们从一个楼层x扔下鸡蛋时,有可能出现两种情况(1)鸡蛋破(2)鸡蛋不破。

1)鸡蛋破,那么我们只需要用剩下的鸡蛋测试 x层以下的楼层; 所以问题简化为x-1层和n-1个鸡蛋
2)如果鸡蛋没有破,那么我们只需要检查比x较高的楼层; 所以问题简化为 k-x 和n个鸡蛋。

最优子结构可以表示为:

k ==> 楼层数
n ==> 鸡蛋数
  eggDrop(n, k) ==>最少需要的测试次数(考虑所有情况)
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x 属于 {1, 2, ..., k}}

下面用递归的方法解决这个问题:

# include <stdio.h>
# include <limits.h>

int max(int a, int b) { return (a > b)? a: b; }

int eggDrop(int n, int k)
{
    // 基本情况
    if (k == 1 || k == 0)
        return k;

    //如果只有一个鸡蛋,最坏的情况下需要k测试
    if (n == 1)
        return k;

    int min = INT_MAX, x, res;

    // 考虑从第1层到底k层扔下鸡蛋的所有情况 的最小结果
    for (x = 1; x <= k; x++)
    {
        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
        if (res < min)
            min = res;
    }
    return min + 1;
}

/* 测试 */
int main()
{
    int n = 2, k = 10;
    printf ("\nMinimum number of trials in worst case with %d eggs and "
             "%d floors is %d \n", n, k, eggDrop(n, k));
    return 0;
}

上面的程序问题是复杂度太大 O(2^k)。如果k=36的话,基本是跑不出结果。

重叠子问题

因为上面的程序重复计算了很多子问题。以E(2,4)为例:

                         E(2,4)
                           |                      
          ------------------------------------- 
          |             |           |         |   
          |             |           |         |       
      x=1/\          x=2/\      x=3/ \    x=4/ \
        /  \           /  \       ....      ....
       /    \         /    \
 E(1,0)  E(2,3)     E(1,1)  E(2,2)
          /\  /\...         /  \
      x=1/  \               .....
        /    \
     E(1,0)  E(2,2)
            /   \
            ......
对于2个鸡蛋,4层楼 部分递归

因此完全可以用动态规划解决。

# include <stdio.h>
# include <limits.h>
int max(int a, int b) { return (a > b)? a: b; }
int eggDrop(int n, int k)
{
    /* eggFloor[i][j] 表示对于 i个鸡蛋 j 层楼,需要的最少测试次数 */
    int eggFloor[n+1][k+1];
    int res;
    int i, j, x;
    // 初始化
    for (i = 1; i <= n; i++)
    {
        eggFloor[i][1] = 1;
        eggFloor[i][0] = 0;
    }

    //只有一个鸡蛋,没得优化,需要j次
    for (j = 1; j <= k; j++)
        eggFloor[1][j] = j;

    // 最优子结构的递推
    for (i = 2; i <= n; i++)
    {
        for (j = 2; j <= k; j++)
        {
            eggFloor[i][j] = INT_MAX;
            for (x = 1; x <= j; x++)
            {
                res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                if (res < eggFloor[i][j])
                    eggFloor[i][j] = res;
            }
        }
    }
    return eggFloor[n][k];
}

/* 测试*/
int main()
{
    int n = 2, k = 36;
    printf ("\nMinimum number of trials in worst case with %d eggs and "
             "%d floors is %d \n", n, k, eggDrop(n, k));
    return 0;
}

参考:http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/


  1. E(2,4) | ————————————- | | | | | | | | x=1/ x=2/ x=3/ x=4/ / / …. …. / / E(1,0) E(2,3) E(1,1) E(2,2) / /… / x=1/ ….. / E(1,0) E(2,2) / ……对于2个鸡蛋,4层楼 部分递归这里的X是什么?不太懂

  2. [email protected]

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1