前段时间有个朋友在问了这个关于鸡蛋和楼层的问题。一开始我也是懵逼的,没弄明白说的是什么意思,且让我从头细细道来。
问题描述
假如给你两个完全一样的鸡蛋,现在有n
层楼高的房子,鸡蛋最高可以从t
层掉下来不会碎,再往上加一层就碎了。请问,最少需要尝试多少次可以得知t
是多少层?
解题思路
如果我没在题目中着重说明是两个鸡蛋,很多人看到题目是都是茫然的。假设你忽略了鸡蛋个数的约束,得到的方案有可能是千变万化的。因为只有两个鸡蛋,所以大家且用且珍惜,一旦碎了,尝试的机会就会大大减少。另外,只要蛋还没碎,是可以重复利用的。
最直观的办法 - 二分法
相信大部分人看到这个问题想到的第一个方法应该是二分法。我们把问题具体化,假如n=100
,那么我们要找的答案就是二分法最坏的情况需要扔多少次。
举例说明,第一次就从 50 层开始扔第一个鸡蛋。
- 假如没碎,我们再从 75 层扔第二次。以此类推
- 假如碎了,那么我们只剩一个鸡蛋了,那么我们只能从第 1 层开始尝试扔第二个鸡蛋,一直扔到到它碎为止。我们把第二次扔碎蛋的楼层指定为
x
,那么t=x-1
。
二分法最坏的情况应该在分支 2 出现,当x=50
时情况最坏。也就说,第一个蛋在 50 层碎了,然后我们很苦逼地从第 1 层开始往上扔,第二个蛋扔到 49 层还没碎。那么说明t
就是坑爹的 49,这时候我们可以得出二分法最坏的结果是n/2
。
进阶的办法 - 等分法
从二分法我们可以看出,其实那并不是一个很好的方案。我们可以在此基础上使用等分的方法来改进。具体的例子如下。
- 将
n
等分为x
等分,使x
的平方大于或等于n
- 在
n=100
的例子里,我们使x=10
- 第一个鸡蛋从第 1 个等分开始扔
- 如果碎了,那么我们从第 1 层开始尝试,最多还需要尝试
x-1
次。 - 如果没碎,我们从第二个等分再扔一次。
- 不管碎了还是没碎,跟外面一层的思路一样。
- 如果碎了,那么我们从第 1 层开始尝试,最多还需要尝试
等分法最坏的情况应该是在最后一个等分出现,比如 100 层楼,当扔到最后一个等分时,也就是 100 层时鸡蛋碎了,那么我们只能从第 91 层开始扔第二个鸡蛋,一直扔到 99 层,蛋没碎,那么最多尝试了2x
次,也就是 20 次。
所以等分法最坏的情况是2x
,并且x**2>=n
最优的解法 - 动态规划
说了这么多,应该到揭示 BOSS 解法的时候了。最优的解法需要动态规划楼层。
我们回到实际的问题中,假如从x
层开始扔第一次,如果碎了就需要再从下往上试x-1
次。这是无论如何也不能避免的事实。
那如果没碎呢,我们可以考虑就往上加x-1
层,如果碎了就从x
层一直尝试到x+(x-1)
层,最多还是x
次。
现在的问题就可以转化为x+(x-1)+(x-2)+...+1
大于或者等于最高楼层。这个加法是不是有一点眼熟,你没看错,其实这就是从 1 一直加到x
,我们可以用初中时学习过的高斯公式表示为x(x+1)/2 ≥ n
。
如果n
是 100 层的话,x
的最小值就是 14,我们开始扔鸡蛋。
- 从
14
楼扔第一次,如果碎了你懂的,从第 1 层开始。 - 如果没碎就往
14+13
层扔,如果碎了你懂的,从第 15 层开始。 - 如果没碎就往
14+13+12
层扔,以此类推。 - 最多尝试次数会小于等于
x
。
写在最后
其实这道题目是一道挺出名的面试题,据说是 Google 家的。如你没能想出完美的办法也是正常的。祝大家国庆玩的开心。