algorithm - 了解两个以上鸡蛋的鸡蛋掉落算法。

Question

http://datagenetics.com/blog/july22012/index.html

我正在使用提到的链接来了解蛋滴问题。我还查看了在线代码，我理解的程度不错(递归有点困惑)，但我似乎无法理解这个鸡蛋掉落问题的一些主要内容。

假设我们有 100 层

对于 2 个鸡蛋，我们说我们从 14 开始，然后转到 14 + (14-1)。我理解为什么我们这样做是为了保持最坏情况的时间统一。但是，我们从哪里开始吃三个鸡蛋呢？该公式表明，在最坏的情况下，3 个鸡蛋最多可尝试 9 次。显然我们不是从 9 开始，因为 9 + ( 9 - 1 ) 不会给我们在 100 中的一致的 9 次试验，那么我们从 3 开始呢？不仅如此，我们如何解决这个问题？

似乎对于 3 个鸡蛋，我们进行了几次试验，直到问题退化为 2 个鸡蛋和 x 个楼层。从概念上讲这是有道理的，但我不明白如何可视化或实现它

我必须在最坏的情况下找到尝试的顺序并实现它，这就是我想要可视化尝试的原因。

我希望这很清楚。这是我的第一颗子弹，这是我的主要问题。如果我遗漏任何信息，请告诉我，我会对其进行编辑。

Answer 1

这个问题可以通过以下 3 种方法(我知道)来解决:

动态规划

使用二叉搜索树的解决方案

通过获得给定数量的鸡蛋和给定的滴数可以测试或覆盖的最大楼层数的直接数学公式来解决

让我先定义一些在之后进行的分析中使用的符号:

e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested or covered with e eggs and n drops

动态规划方法的关键在于以下 Fmax 的递归公式:

Fmax(e, n) = 1 + Fmax(e-1, n-1) + fmax(e, n-1)

而获得 Fmax 的直接数学公式的关键在于以下 Fmax 的递推公式:

Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n) + n 

对于这个问题，使用二叉搜索树 (BST) 的替代解决方案也是可能的。为了方便我们的分析，我们画出BST，稍作修改如下:

1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side

如果我们用上述表示方式绘制 BST，那么 BST 的宽度代表鸡蛋的数量。

任何具有 f 个节点的 BST，以上述表示形式绘制并受到 BST <= e(鸡蛋数)的约束宽度是一个解决方案，但它可能不是最佳解决方案。

因此，得到最优解相当于得到 BST 中节点的排列，其最小高度受到约束: BST 的宽度 <= e

有关以上 3 种方法的更多详细信息，请查看我的博客: 3 approaches for solving generalized egg drop problem