“扔鸡蛋” 、“在X星球摔手机” —— 谷歌面试/蓝桥杯决赛

题目:有a个完全一样的鸡蛋,有b层楼,想测鸡蛋的坚硬度 R( 坚硬度R不会小于0 )。测试方法是,如果将一个鸡蛋从第x层扔出,砸到地面(第0层),如果碎了,鸡蛋的坚硬度R值就是 x (有些题目认为此时坚硬度应该是 x-1 而不是 x,其实只是取值方式不一样,问题本质没变,本博客中认为是x而不是 x-1 )。因为只有b层楼,所以R肯定不会大于b。现在题目给定一个a和b,问,运气最坏的情况下,最少尝试多少次可以保证测出鸡蛋的坚硬程度,题目保证有且只有一个最优解。

这是谷歌原创的面试题,原名是“扔鸡蛋” 。蓝桥杯里叫“X星球摔手机”。

读懂题目

题目输入两个正整数a和b,要求我们输出一个正整数答案,我们假设这个正整数答案为 int F(int a, int b) 这个函数的返回值,则问题转化为设计函数 F(a,b)。

最坏情况:首先,如果你运气无限好,欧皇之皇,你只要有1个鸡蛋,就可以1次测出坚硬度。这样问题就没有意义了,所以题目限定了最坏情况,所以你在思考时,只考虑最差情况。

保证测出:假设只有1个鸡蛋,有100层楼。如果想测出鸡蛋坚硬度,最坏运气情况下要尝试100次,即第一层扔一次,第二层扔一次….一直到第100层,一共一百次。如果不这么做,你就有可能测不出来坚硬度R了。比如,第一次扔第一层,没碎,第二次扔第三层,碎了,那么你手上就没有鸡蛋了,就不能继续扔了,就测不出来坚硬度R是2还是3了。所以,要满足题目的“保证”性。

最少次数:如果有100个鸡蛋,只有1层,显然只需要1次即可测出坚硬度R,当然你可以扔100次,但是你只测1次就能在满足题意的情况下测出坚硬度R了,所以答案是1而不是100。

根据读题我们得出,满足题意的情况下:

  • 1个鸡蛋100层, F(1,100)=100; 推导出 F(1,n)=n
  • 100个鸡蛋1层,F(100,1)=1; 推导出 F(n,1)=1
  • 0个鸡蛋n层, F(0,n)=无解; 题目保证不会出现这个情况(函数也可以返回0,代表无解)

F(1,n)=n 和 F(n,1)=1 这两个结论在动态规划解法中会用到

解法一:二分

这是很容易想出来的方法。思路是类似于二分(折半)查找。

以a=2, b=100为例, 把鸡蛋从一半楼层(100/2=50层)往下扔。

  • 如果第1枚鸡蛋在50层碎了,为了刚才提到的“保证性”,第2枚鸡蛋就从第1层开始扔,然后从第二层开始扔…一层一层增长,一直扔到第49层,这样就扔了50次(最坏情况下)。
  • 如果第1枚鸡蛋在50层没碎,则继续二分,在剩余楼层的一半(即50+(50/2)=75层)往下扔,然后判断这第1枚鸡蛋的这个第二次扔有没有碎:如果没碎就再折半,如果碎了就用上方提到的方法一层一层来试。如此递归,直到求出答案。

满足题意的情况下,最少需要尝试50次。得出的 F(2,100)=50。这种方法显然不是最优解,即 F(2,100) 可以有小于50的返回值。

想法二:平方根

根据上面的想法而改进出来的方法。在 a=2, b=100 的情况下,上面的方法中第一枚鸡蛋和第二枚鸡蛋的尝试次数相差甚大,这也是上面解法得出的答案过多的原因(第二枚鸡蛋每次扔下去只能带走1层的可能性)。如何均衡它们的次数呢?

做一个平方根运算,100的平方根是10。因此,我们尝试每10层扔一次,第一次从10层扔,第二次从20层扔,第三次从30层……一直扔到100层。最坏的情况是在第100层碎掉,尝试次数为 10(刚才那10次) + 9(测试91层,92层,93层…99层) = 19次。这样,每个鸡蛋都能带走10层的可能性。

根据这个解法,得出的F(2, 100)=19。然而,这个解法还有点小优化。

从15层开始扔(而不是第10层),接下来是25层、35层……一直到95层,第95层碎了(最坏情况下就是这样),然后再试86、87、88、89、90、91、92、93和94层。 尝试次数为 9 + 9 = 18次。即 F(2,100)=18。

特定条件下的最优解:解方程

根据以上两种方法,设计的F(a,b)函数能解决这个问题(能在满足题目的条件下测出坚硬度R)并得出一个答案,只是 F(a,b) 的返回值还是比较大,所以我们称以上的两种方法是解而不是最优解。接下里的这个解是一个最优解,即用这个方法得出来的 F(a,b) 一定是最小的。

这个方法比较特殊,只能在a为2时使用。但是不失为一种学习的方法。上述的两种方法道理也是一样的,虽然不能得出最优的解,但也是我们学习的过程中可以学习的方法,它们存在的目的不是为了解题,而是学习。就像冒泡排序,因为时间复杂度太高而没有任何人会用它,它存在的意义在于教学,冒泡排序也是排序问题的一种解。

说回解法本身,这个解法在满足a=2时得出的答案肯定和下面的动态规划得出的结果是一样的。这个解法是一个结论,即:假设F(a,b) = x,x为最优解,那么扔鸡蛋的层数为x。

解法烧脑,可以跳过。

假设第一次扔在第x层:

  • 如果鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-1层。 总共尝试了x-1+1 = x次
  • 如果鸡蛋没碎,此时问题转换为在剩下的(100-x)楼层中按照这个方法来扔,剩余扔的次数为x-1次,所以扔在剩下楼层中的第x-1层,递归重复。

这样一来,最坏情况下,第一次鸡蛋就碎了。总共尝试了x-1+1 = x次,符合假设次数。 如果你们觉得最坏情况可能更坏,可以自己去尝试,你会发现,最坏情况可能有很多种,但是“ 第一次扔鸡蛋就碎了 ”这种情况一定是最坏情况。

这里为了方便理解我直接给出答案,根据动态规划的解,F(2,100)最优解为14,最坏情况下为第一个鸡蛋第一次扔就碎了,一共扔了14次,从先扔14层,然后从第一层开始扔到第13层。如果鸡蛋一直没碎,则可能不是最坏情况,尝试的所有楼层为:14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100。共尝试12次。可以看到,第一次扔了第14层,没碎的话第二次扔的不是14+14=28层而是14+13=27层,因为第二次扔时剩余扔的次数 x 变为 x-1 ,所以第二次扔在剩余楼层的第 x-1 层而非第 x层,所以加13。

第一次扔到第x层,第二次扔到剩下楼层的第x-1层….所以各次扔鸡蛋的楼层跨度之和为f(x)=x + (x-1) + (x-2) + … + 1 ,此处b为100,令f(x)=100,求出并向上取整得到x=14

假设第一次扔在第x+1层:

  • 如果鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x层。
  • 如果鸡蛋没碎, 则在剩下的(100-(x+1))楼层中按照这个方法来扔,递归重复。

用这个方法,最坏情况下就是第一次扔鸡蛋就碎了,总共尝试了x+1次,所以,如果第一次不扔在x层而是在x+1层,会导致尝试次数变多。由此可见,第一次扔的楼层必须小于x+1层,否则尝试次数会变多,一定不是最优解。

假设第一次扔在第x-1层:

  • 如果鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-2层。
  • 如果鸡蛋没碎,则在剩下的(100-(x-1))楼层中按照这个方法来扔, 剩余扔的次数为x-1次,所以扔在剩下楼层中的第x-1层, 递归重复。

这样一来, 如果第一次扔第一个鸡蛋就碎了, 总共尝试了x-2+1 = x-1次,看起来好像比最优解好?其实并不是,因为如果按照这个方法来扔,“ 第一次扔鸡蛋就碎了 ”这种情况不再是最坏情况了。如果用这个方法,最坏情况是“ 鸡蛋坚硬度R为b ”,而非“ 第一次扔鸡蛋就碎了 ”。

还是a=2,b=100的例子。假设扔在x-1层是可取的,那么f(x)=(x-1)+(x-2)+…+0,令x=14,f(x)=93而不是100,可知,在14次内,这种方法无法保证在100层且满足其他题意的条件下,测出鸡蛋的坚硬度R。所以最坏的情况是R=100,此时扔13次测到93层,还要继续测94、95…100层,明显不是最优解。 由此可见,第一次扔的楼层必须大于x-1层,否则尝试次数会变多,一定不是最优解。

综上所述,要想尽量楼层跨度大一些,又要保证不超过假设的尝试次数x,那么第一次扔鸡蛋的最优选择就是第x层,扔在x+1层或者x-1层都不是最优解,即,结论:“假设F(a,b) = x,x为最优解,那么,扔鸡蛋的层数为x”成立。

标准最优解:动态规划

当a>2时,上面那个谷歌工程师想出来的方法不再成立。本题目中,问题显然无后效性。

假设我们第一个鸡蛋扔出的位置在第x层(1<=x<=b),只有两种情况,要么碎了,要么没碎:

  1. 鸡蛋没碎,那么剩余的b-x层楼 需要尝试 ,剩余a个鸡蛋,那么F(a,b)可以转变为下面的函数:F(a, b-x)+ 1( 其中1<=x<=b )
  2. 鸡蛋碎了,那么只剩下从1层到x-1层楼需要尝试,剩余的鸡蛋数量是a-1,F(a,b) 可以转变为下面的函数: F(a-1, x-1)+ 1 ( 其中1<=x<=b )

整体而言,我们要求出的是a个鸡蛋 b层楼条件下,最大尝试次数最小的解,所以这个题目的状态转移方程式如下:
F(a,b)= Max( F(a,b-x)+1,F(a-1,x-1) +1 ) ( 其中1<=x<=b )

又因为,F(1,n)=n, F(n,1)=1, 所以,不管a和b取值如何,F(a,b)最终都能解出来。 时间复杂度为O(a*b*b),空间复杂度为 O(a*b) 。

举个例子,F(2,2)= Max(  F(2,2-x)+ 1, F(2-1,x-1) + 1 ) (其中x=1或x=2)式子要尝试2次,第一次是x=1的情况: F(2,2) = Max(1+1, 0+1) = 2,第二次是x=2的情况: F(2,2) =Max(0+1, 1+1) = 2,也就是说,不管x是1还是2,解出来都是2,不管第一次扔在第一层还是第二层,2个鸡蛋2层楼问题,在满足题意的条件下都只需要2次即可测出坚硬度。

再举个例子, F(3,2)= Max(  F(3,3-x)+ 1, F(3-1,x-3)+ 1 )(其中x=1、2、3) 式子要尝试3次, 第一次是x=1的情况:F(3,2) = Max( 2+1, 0+1 ) = 3 ,第二次是x=2的情况: F(3,2) =Max( 1+1, 1+1 ) = 2,第三次是x=3的情况: F(3,2) = Max(1, 2+1) =  3 。因此,在2个鸡蛋3层楼的情况,最优的方法是第一个鸡蛋在第2层扔,共尝试2次。 而不是扔在第一层或者第三层。

代码实现

#include <bits/stdc++.h>
int f1(int eggNum, int floorNum){
        if(eggNum < 1 || floorNum < 1) {
            return 0;
        }

        //开一个dp数组,值表示eggNum个鸡蛋,floorNum层楼条件下的最优化尝试次数
        //注意,如果题目中dp数组太大,请开到堆中而不是放到运行栈中
        int dp[eggNum+1][floorNum+1];

        //初始化
        for(int i=1;i<=eggNum; i++){
            for(int j=1; j<=floorNum; j++) {
                dp[i][j] = j;
            }
        }

        for(int n=2; n<=eggNum; n++){
            for(int m=1; m<=floorNum; m++){
                for(int k=1; k<m; k++){
             //扔鸡蛋的楼层从1到m枚举一遍
             //如果当前算出的尝试次数小于上一次算出的尝试次数,则取代上一次的尝试次数。
             //这里可以打印k的值,从而知道第一个鸡蛋是从第几层扔的。
                    dp[n][m] = min(dp[n][m], 1+max(dp[n-1][k-1],dp[n][m-k]));
                }
            }
        }
        return dp[eggNum][floorNum];
    }

优化空间复杂度

如果深入学习过动态规划,不难发现本解中的动态规划可以用滚动数组来优化,从而节省空间。空间复杂度降到O(b) 。此处就不给代码了。

参考资料