拼图| 35组（2个鸡蛋和100层）

下面是这个著名谜题的实例描述，其中包括两个鸡蛋和一栋100层的建筑。

假设我们想知道，在一栋100层的建筑中，哪些楼层可以安全地投下鸡蛋，哪些楼层会导致鸡蛋在落地时破裂。应该使用什么策略来落蛋，以使最坏情况下的总滴数最小化，并找到所需的地板

我们可以做一些假设：

• 一枚能在坠落中存活下来的蛋可以再次使用。
• 破鸡蛋必须扔掉。
• 跌落对所有鸡蛋的影响都是一样的。
• 如果鸡蛋掉下来会碎，那么它从更高的地板上掉下来就会碎。
• 如果一只蛋能在一次坠落中存活下来，那么它能在一次较短的坠落中存活下来。

我们强烈建议您尽量减少浏览器，并先自己尝试

如果 只有一个鸡蛋 为了确保得到正确的结果，实验只能用一种方法进行。把鸡蛋从一楼的窗户扔下来；如果它还活着，就把它从二楼的窗户扔下来。继续向上直到它断裂。在最坏的情况下，这种方法可能需要100个粪便。 假设有两个鸡蛋。保证在所有情况下都有效的蛋液最少是多少？ 问题其实不是找到临界楼层，而是仅仅决定从哪个楼层投下卵子，从而使试验总数最小化。

如果我们使用 二进制搜索法 为了找到楼层，我们从50层开始，然后在最坏的情况下进行50次比较。最坏的情况发生在所需楼层为49层时。

优化方法： 我们的想法是使用以下等式优化解决方案：

Let us make our first attempt on x'th floor. If it breaks, we try remaining (x-1) floors one by one. So in worst case, we make x trials.If it doesn't break, we jump (x-1) floors (Because we havealready made one attempt and we don't want to go beyond x attempts.  Therefore (x-1) attempts are available),    Next floor we try is floor x + (x-1)Similarly, if this drop does not break, next need to jump up to floor x + (x-1) + (x-2), then x + (x-1) + (x-2) + (x-3)and so on.Since the last floor to be tried is 100'th floor, sum ofseries should be 100 for optimal value of x. x + (x-1) + (x-2) + (x-3) + .... + 1  = 100 x(x+1)/2  = 100         x = 13.651Therefore, we start trying from 14'th floor. If Egg breaks on 14th floorwe one by one try remaining 13 floors, starting from 1st floor.  If egg doesn't breakwe go to 27th floor.If egg breaks on 27'th floor, we try floors form 15 to 26.If egg doesn't break on 27'th floor, we go to 39'th floor.An so on...

最佳试验次数为14分钟 这个 最坏的情况。

参见下文，了解一般k层和n层的编程解决方案。 https://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/

本文由 拉希特 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论