蛋蛋破碎的临界点

题目描述

小明有两个鸡蛋，他面前有一栋100层的高楼，如果要测出鸡蛋破碎的临界楼层，在最坏的情况下，最少需要把鸡蛋从楼上丢下来几次？

鸡蛋在没碎的情况下可以重复使用。

解释一下题目中说的最坏的情况是啥意思，比如你有一个方案，从100层丢下一个鸡蛋，有下面两种情况：

1. 鸡蛋没碎，这个时候只要1次就找到了临界楼层，但这不是题目中要求最坏的情况。
2. 鸡蛋碎了，这个时候你需要用另一个鸡蛋从1楼开始到99楼一层一层的尝试，最终发现鸡蛋在第99层碎了或者依然没碎，需要99 + 1 = 100 次，这就是题目中想要表达的最坏的情况。

总结一下，最坏的情况就是你的方案最多需要把鸡蛋从楼上丢下多少次可以确定临界楼层，题目意思的是要你在众多方案中找到鸡蛋从楼上丢下来次数最少的那个方案。

思路解析

不少同学看到这里已经麻了，大脑一片空白，不要慌，下面我来一步步带领大家解析这道题目。

一些脑袋灵光的同学一下就想到使用二分法来试试，那么二分法最坏的情况下需要几次呢？

首先从50层丢下第一个鸡蛋，有下面几种情况：

1. 鸡蛋没碎，这个时候还有两个鸡蛋，换到75层丢下第一个鸡蛋，如果鸡蛋依旧没碎，依次类推，假设在[50, 100]层之间每次第一个鸡蛋都没碎，这样需要log₂100 = 6.6次。
2. 鸡蛋碎了，这个时候需要用另一个鸡蛋从1楼到49楼一层一层的尝试，一直到49层鸡蛋也没碎或者碎了，这样需要 49 + 1 = 50次。
3. 第一个鸡蛋在(50, 100]层之间的某一次碎了，这个时候最坏的情况下需要尝试的次数不会超过50次，因为对x层采用二分，如果最坏尝试次数为x/2，要满足 x/2 + 1 > x成立，那么x < 1，这里x = 50，所以这种情况下最坏尝试次数不会超过50次。

综上，采用二分法最坏的情况是50次。

如果尝试三分法，四分法，甚至十分法呢？

我们继续讨论一下采用十分法的情况， 把100层楼分成10份，先从10楼丢下第一个鸡蛋，有下面几种情况：

1. 鸡蛋没碎，这个时候还有两个鸡蛋，下一次第一个鸡蛋需要从20楼丢下，依次类推，假设在[20,100]层之间每次第一个鸡蛋都没碎，这样需要尝试10次。
2. 鸡蛋碎了，这个时候需要用另一个鸡蛋从1楼到9楼一层一层的尝试，一直到9楼鸡蛋也没碎或者碎了，这样需要尝试 9 + 1 = 10次。
3. 第一个鸡蛋在[20,100]层之间某一次碎了，假设为x层，其中x是10的倍数(因为是十分法)，总共需要尝试(x / 10) + 9次，x = 100时，为最坏的情况，需要19次。

综上，采用十分法的最坏情况是19次。

下面我们用数学来推导一下最优的一种方案。

假设最优的方案最坏的情况下需要尝试x次，那么第一次需要从第几层丢鸡蛋呢？如果从y层丢鸡蛋，需要保证鸡蛋在碎和不碎的情况下尝试次数都不能超过x。

1. 如果鸡蛋碎了，那么需要用第二个鸡蛋从1楼到y - 1楼一层一层尝试，这时最坏情况尝试次数为y，需要保证y <= x。
2. 如果鸡蛋没碎，那么确定鸡蛋在剩下区间(y,100]的临界楼层，最坏情况下尝试不能超过x - 1次。

为了保证快速定位临界楼层，只有y值越大，剩下的楼层越少，定位速度才越快，所以这里取y的最大值y = x，有点贪心的思想在里面。

在第一次鸡蛋没碎的情况下，还剩两个鸡蛋，还有100 - x层要定位，可以把问题转换成利用两个鸡蛋寻找100 - x层楼鸡蛋破碎的临界楼层。

按照上面的讨论，剩下的100 - x层最多尝试次数为x - 1，这次第一个鸡蛋要从x - 1层丢下。如果鸡蛋碎了需要再用第二个鸡蛋尝试x - 2次，如果鸡蛋没碎问题就转换成了利用两个鸡蛋寻找100 - 2x - 1层楼鸡蛋破碎的临界点，剩下的100 - 2x - 1层最多尝试次数为x - 2，相应的第一个鸡蛋要从x - 2层丢下。

依次类推，最终每次丢鸡蛋的楼层的和至少为100，我们可以得到一个公式 x + (x - 1) + ... + 1 >= 100，即x(x + 1)/2 >= 100，可得x = 14。

综上，在每次鸡蛋都不碎的情况下，依次从14层，14+13=27层，14+13+12=39层，....，100层抛下，最坏的情况下需要尝试14次。

最后我们通过程序员的逻辑来分析这个问题。

定义dp[n]表示n层楼两个鸡蛋寻找破碎的临界楼层最坏情况下需要尝试最少的次数，假设从k层丢下第一个鸡蛋，那么存在两种情况：

1. 鸡蛋没碎，问题就转换成了子问题n - k层楼两个鸡蛋寻找破碎的临界楼层最坏情况下需要尝试最少的次数，dp[n] = dp[n-k] + 1。
2. 鸡蛋碎了，利用第二个鸡蛋从1楼到k - 1楼一层一层尝试，这时dp[n] = k。

综上，从k层丢下第一个鸡蛋最坏情况下dp[n] = max(dp[n-k] + 1，k)。 当k是一个变量时，k的每个值都代表一种方案，我们的目的是在众多方案中寻找尝试次数最少的一种，所以前面的公式就变成dp[n] = min(max(dp[n-k] + 1，k))，其中k = 1，2，...，n - 1。

再看下边界条件，很显然dp[1] = 1，dp[2] = 2。

这不就是动态规划么，通过上面的讨论我们确定了状态转移公式和边界条件，代码实现如下。

#include <iostream>
#include <algorithm>
using namespace std;

int dp[101];

int main() {
    dp[1] = 1;
    dp[2] = 2;
    int min_times = 101;
    for (int i = 3; i <= 100; i++) {
        min_times = i;
        for (int k = 1; k < i; k++) {
            min_times = min(min_times, max(dp[i - k], k - 1) + 1);
        }
        dp[i] = min_times;
    }
    cout << dp[100] << endl;
    return 0;
}

运行上面的代码，输出为14。

通过上面的分析我们可以知道最优方案的最坏情况14次就能确定100层楼鸡蛋破碎的临界楼层。

聪明的你能找出m层楼，n个鸡蛋的情况下寻找鸡蛋破碎临界楼层的最优方案吗？