两个鸡蛋的问题

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

问题描述

假如给你两个完全一样的鸡蛋，现在有n层楼高的房子，鸡蛋最高可以从t层掉下来不会碎，再往上加一层就碎了。请问，最少需要尝试多少次可以得知t是多少层？

如果我没在题目中着重说明是两个鸡蛋，很多人看到题目是都是茫然的。假设你忽略了鸡蛋个数的约束，得到的方案有可能是千变万化的。因为只有两个鸡蛋，所以大家且用且珍惜，一旦碎了，尝试的机会就会大大减少。另外，只要蛋还没碎，是可以重复利用的。

相信大部分人看到这个问题想到的第一个方法应该是二分法。我们把问题具体化，假如n=100，那么我们要找的答案就是二分法最坏的情况需要扔多少次。

举例说明，第一次就从 50 层开始扔第一个鸡蛋。

二分法最坏的情况应该在分支 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，我们开始扔鸡蛋。

其实这道题目是一道挺出名的面试题，据说是 Google 家的。如你没能想出完美的办法也是正常的。祝大家国庆玩的开心。