algorithm - 三蛋问题

Question

我刚刚在读The Two Egg Problem :

The Two Egg Problem

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

我一直在跟进，直到“看，我能做三件事”部分。作者指出，在第一个鸡蛋破裂后，它会退化为 2 个鸡蛋问题，并且可以递归解决。

这很好，但是当使用 3 个鸡蛋而不是 2 个(第一个鸡蛋)时，我们不想选择更大的步长吗？我们从哪一层扔第一个鸡蛋？

有了 1 个鸡蛋，我们必须从 1 楼开始。
有了 2 个鸡蛋，我们求解 n(n+1)/2=k 并四舍五入，其中 n 是起始楼层，k 是楼层数。
对于 3...我在想出一个公式时遇到了麻烦。

---

再考虑一下，有 2 个鸡蛋，最大掉落次数等于我们掉落第一个鸡蛋的楼层数。例如，有 2 个鸡蛋和 100 层楼，解决方案是 14，这意味着我们从 14 楼放下第一个鸡蛋，如果它破了，我们必须再跌落 13 次，从 1-13 楼。

用 3 个鸡蛋，解决方案是 9(如图所示)。但是我们不想在第 9 层扔第一个鸡蛋，我们可以把它扔得更高，因为我们不必在中间迭代 1s。

如果我们再次从 14 层开始扔，它坏了，那么我们递归。 n(n+1)/2=k 其中 k 现在是 13... 但是这给了我们 4.815，如果我们 ceil 加上我们之前的下降我们得到6，低于实际解，所以这里有些地方不对...

---

Answer 1

If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...

如果它不坏怎么办？然后你有一个 86 层的三蛋问题，它可能比 100 层的问题少掉一滴。

假设您从 50^th 层放下第一个鸡蛋。如果它坏了，你就会遇到 49 层楼的两个鸡蛋问题，最多需要额外掉落 10 次。因此，这将为您提供 11 次掉落的最坏情况(因为如果它没有破裂，50 层的三颗鸡蛋问题最多需要额外 7 次掉落)。

如果你选择 37^th 层作为第一次掉落，如果它坏了，你就有了 36 层的二蛋问题，最多需要 8 次额外的掉落。如果不破，你还有一个63层的三蛋问题。你想用最多 8 次掉落来解决这个问题，所以如果下一次掉落打破了鸡蛋，剩下的两个鸡蛋问题应该最多可以在 7 次掉落中解决，因此你可以为第二次掉落选择的最高楼层是 37 + 28 + 1 = 66，因为 28 层是最高的，您最多可以用 7 个水滴和两个鸡蛋解决。如果鸡蛋没有破，你有一个 34 层的三鸡蛋问题，还剩 7 滴。如果鸡蛋破了 21 (6*7/2)，那么用剩下的 6 滴肯定能解出的最高数，所以你可以选择 floor 66 + 21 + 1 = 88。如果鸡蛋没有破，你还有 12 层楼还有 6 次掉落，这已经可以只用两个鸡蛋了。

系统地，您可以用 d 掉落和 e 鸡蛋解决的最高楼层数是

          / 1, if d == 1
F(e,d) = |  d, if e == 1
          \ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1

如果你只有一滴，你别无选择，只能选择你还不知道鸡蛋不会破的最低层。如果那打破了它，而你尝试了更高的楼层，你不知道第一层打破鸡蛋。

如果你只有一个鸡蛋，你必须按顺序检查每一层，直到鸡蛋破裂或用完掉落物为止。

否则，如果第一次掉落的楼层高于 F(e-1,d-1) + 1，那么如果鸡蛋破裂，您可能找不到第一个破裂的楼层。如果第一次掉落是从较低的楼层开始的，那么如果鸡蛋没有破裂，你将无法通过 d-1 次掉落到达那么高，所以第一次掉落应该是从 F( e-1,d-1) + 1。如果它坏了，你可以用剩余的 e-1 鸡蛋和 d-1 假设掉落来解决。如果没有，您可以用剩余的水滴和鸡蛋解决下一个 F(e,d-1) 层。

相反，要找到带有 e 个鸡蛋的 f 层可能需要掉落多少次，您必须找到

D(e,f) = min { d | F(e,d) >= f }

可以通过计算F(e,d)矩阵找到，也可以使用动态规划:

如果第一次掉落选择s层，如果鸡蛋破了，最多需要D(e-1,s-1)次掉落来确定地面。如果鸡蛋没有破，您最多需要跌落 D(e,f-s) 次才能确定地板。因此，为第一滴选择 floor s 的最坏情况是

WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }

最坏情况中最好的情况是

D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }

(当然 D(e,0) = 0)。