经典面试问题-丢鸡蛋
文章目录
1. 题目介绍
扔鸡蛋是一道经典的面试题，具体问题是给出 N (N>=2)个鸡蛋，以及M层楼房(M>=N)，要求计算最少需要多少次/平均需要多少次能得出鸡蛋在第几层正好摔碎。 这道题根据鸡蛋的个数以及其他要求，衍生出了很多变种，这里将整理部分题型及其思路。
2. 解决思路
一般来说，可以分为鸡蛋(或玻璃球)有限制和无限制两种情况，在无限制的情况下，题目一般要求给出最佳的求解方案；在有限制的情况下，题目一般要求给出平均丢掷次数最少的方案。
2.1 鸡蛋个数无限制
我们先讨论鸡蛋个数无限制的情况。当可以无数次丢掷鸡蛋来寻找正确层数时，这个问题就可以简化为一个查找问题。而最快的查找自然是二分查找算法，每次都以楼层的一半作为测试点，缩小查找范围。
2.2 鸡蛋个数有限制
当然，更多的情况还是鸡蛋个数有限制，最常见的有2个鸡蛋和3个鸡蛋。在这种情况下，鸡蛋一旦摔碎意味着少了一次测试机会，因此需要解决的问题比无限制的情况更多。
2个鸡蛋
- 暴力二分法 看到这个问题的第一反应，肯定还是和无限制情况下一样，首先想到是否能用二分法来进行查找。但与上面个数无限制不同，一旦我们在二分的过程中摔碎了一个鸡蛋，剩下就必须从没碎的那一层开始，一层层的往上找了。 因此，在最差的情况下，也就是对于M层楼来说，在第 2/M 层楼向下丢掷鸡蛋时碎了，则需要遍历 2/M 次。
- 比例划分法 在二分法无法得到很好结果的情况下，我们考虑对其进行优化。首先很容易就可以想到，将M层楼均分成x等分，每等分含y层楼。每次都从第 y + i 层楼向下扔，如果碎了就查找 (y + i -1, y + i) 区间，如果没碎就将 i + 1并重复上一步。 在这种情况下，第一颗鸡蛋用于确认区间，其最好和最差情况分别为 1 和 x 次，第二颗鸡蛋用于遍历，最好和最差情况为 1 和 y 次。如果我们希望第一个和第二个鸡蛋扔的平均次数接近，那么x和y的大小应该保持一致。那么对于 x^2 = M，我们可以得出x的大小应该为楼层数M的平方根。
- 均值求解法 上面的比例划分方法其实是将"确定区间"和"寻找确切层数"两个动作分开来求平均次数的，但实际上我们要求的是无论鸡蛋在哪一层正好摔碎，都应该有相近的测试次数。 我们还是用对M层楼进行划分的方式，假设鸡蛋在第一个划分点就摔碎，则最差的遍历次数是 (1 + n0)，其中 1 代表在划分点投掷的一次，n0 代表第一个划分区域的长度。那么假如鸡蛋第一个点没碎，而第二个点碎了，则最差情况为 (1 + 1 + n1)，n1代表第二个划分区域的长度，如下图所示。
以此类推直到最后一个区域。按照我们之前的思路，每种情况的次数应该是大致相同的，也就是说应该有 1 + n0 = 2 + n1 = 3 + n2 …，每一个区域的层数是向下递减的。那么此时我们就可以根据总楼层M求解初始区域的层数。 有 n0 + n1 + n2 + … = M, 将上式带入可得 n0 + n0 - 1 + n0 - 2 … + 1 = M，根据等差数列公式求解得到 n0(n0 + 1)/2 = M，解出来的n0即将初始层数。
3个或者更多个鸡蛋
其实当这道题回归到多个鸡蛋求解时，就可以发现这其实是一道常见的动态规划题目了。 按照动态规划的步骤，首先我们要找出该问题的子问题是什么。原始问题是求M层楼x个鸡蛋，最坏需要投掷多少次才能检测出鸡蛋正好摔碎的楼层。当丢出一个鸡蛋之后，问题就减小为M-n层楼，用x/x-1个鸡蛋最坏需要多少次，这里的n是我们的划分区域大小。
根据这样的思路，再来考虑状态转移方程。假设当前在n层楼，还剩下x个鸡蛋，表示为 f(n, x)，那么当前投掷鸡蛋要是碎了，下一个求解的问题可以表示为 f(n - 1, x - 1)，如果没碎，可以表示为 f(M - n, x)。那么可得求最差结果的方程 f(n, x) = max( 1 + f(M-n, x), 1 + f(n - 1, x - 1))。 之后无论是用递归的方式还是数组的方式都可以容易的计算出最差/平均投掷次数。
更详细的分析和代码这里就不放了，但理解了动态规划的思路，无论多少个鸡蛋也能理解这个题型的用意了。