鸡蛋从三米高落下哪些物体不会碎（用2个鸡蛋从100层楼层里寻找扔下鸡蛋不碎最高楼层的最小尝试次数）

Google有道面试题，特别经典而且网上讨论和解法很多，原文如下：，下面我们就来聊聊关于鸡蛋从三米高落下哪些物体不会碎?接下来我们就一起去了解一下吧!

鸡蛋从三米高落下哪些物体不会碎

Google有道面试题，特别经典而且网上讨论和解法很多，原文如下：

Google Interview Puzzle : 2 Egg Problem *You are given 2 eggs. *You have access to a 100-storey building. *Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. *You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

即系，请你用两个鸡蛋，从一栋100层楼栋里找到扔下鸡蛋不碎最高楼层的最小尝试次数。首先，我们先认识几个事实：

1. 如果从x层（0<x<=100）扔下鸡蛋不碎, 那么小于x层扔下鸡蛋肯定不碎；
2. 如果x层扔鸡蛋碎了，那么大于x层扔鸡蛋肯定会碎，鸡蛋个数减1；
3. 如果鸡蛋在第一层就碎了，那么最小尝试次数为1，不管你有多少个鸡蛋；
4. 即使从100层扔下，鸡蛋还是有可能不碎的（避免鸡蛋易碎惯性思维）；
5. 前一个鸡蛋扔碎，剩最后一个鸡蛋时，你只能从该阶段底层开始依次扔。所以，如果两个鸡蛋情况下最小尝试次数为s，那么第一个鸡蛋碎的楼层大于或等于s。

题外话，有些事实显而易见，但很多时候解算法题时，一步步理清所有条件和事实，是很有必要的。因为将抽象的东西具体化，你会踏实很多，思绪更清晰。

也许，很多人第一想法是二分查找，先在第50层扔，如果鸡蛋碎了，再从25层扔？到这一步，我们应该警醒了，此时只有一个鸡蛋，如果鸡蛋再碎，我们将无法找到问题的解。

但可以从1到49逐级往上扔，最坏情况下找到问题解需要50（50-1 1）次。如果50层鸡蛋没碎，可从75层扔，以此类推，最坏情况下找到问题解需26（74-50 2）次。

二分查找，在最好的情况下我们仅需进行7次尝试，但问题是要使用最优策略在最坏情况的解，所以7次并不是我们要找的。

假设在最优策略下，最坏情况的尝试次数为x。

然后，我们从第x层开始扔鸡蛋，因为如果此时鸡蛋碎了，我们需要从1、2、3、....、x-2到x-1逐级往上扔，需要的次数刚好等于x；

1. https://brilliant.org/wiki/egg-dropping/

2. https://leetcode.com/articles/super-egg-drop/