两个鸡蛋的问题
Post

两个鸡蛋的问题

前段时间有个朋友在问了这个关于鸡蛋和楼层的问题。一开始我也是懵逼的,没弄明白说的是什么意思,且让我从头细细道来。

问题描述

假如给你两个完全一样的鸡蛋,现在有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次。
    • 如果没碎,我们从第二个等分再扔一次。
      • 不管碎了还是没碎,跟外面一层的思路一样。

等分法最坏的情况应该是在最后一个等分出现,比如 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 家的。如你没能想出完美的办法也是正常的。祝大家国庆玩的开心。

读书 - 《挪威的森林》

读书 - 《无声告白》