从建筑物上扔鸡蛋

Question

这是来自Robert Sedgewick的《算法（第四版）》中的练习问题1.4.24。

Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.

虽然lgN的解决方案很容易想到，但我完全不知道2lgF的解决方案。无论如何，由于我们没有给出F的值，因此2lgF解决方案的基础在哪里？

有人能为这个问题提供一些提示吗？谢谢。

- Guibao Wang

---

这是一个搜索问题，给定一个有序集合。也许这可以帮助 :)。 - Randy

嗨，Randy，有没有相关链接或更多阅读资料？ - Guibao Wang

在建筑物上进行二分查找，从n/2楼落下，如果破碎了，则向下走n/4，以此类推。因此，您最多可能会打破lgN个鸡蛋，并在lgN步内到达该点。 - Elbek

可能是广义的两个蛋问题的重复。 - David Eisenstat

Answer 1

logN：从顶部开始，总是将搜索空间减半 -> 二分查找

2 * logF：从1开始，接下来是2、4、8（即2 ^ i），一旦鸡蛋在经过logF步后碎了，则在较小的搜索空间中进行二分查找（范围＜F，因此搜索次数＜log F） -> 指数搜索

- b.buchhold

---

很好的解释，非常有用。@timothy-shields你的解决方案也很好，非常感谢。 - Guibao Wang

那又如何决定F的值呢？ - Pavel

我不明白在lgN部分，如果我们保持分割，最后会到达第1层，但是如果F = 7且N = 8怎么办？我们不会得到lgN个破碎的鸡蛋。在2lgF部分，我也不明白我们如何得到2lgF个破碎的鸡蛋，听起来像你只需要进行2lgF步，但你破碎的鸡蛋数量为1。 - Pavel

哦，好的，抱歉，我以为这个练习的重点是要达到给定数量的破碎鸡蛋，但实际上是要找到F，谢谢。我经常对这些练习感到困惑，大多数时候我不理解它们在问什么。 - Pavel

Answer 2

< p > lg(F) 的解决方案是进行 1, 2, 4, 8, ... 直到第一个鸡蛋在 2^(k+1) 处破裂，然后在 2^K 到 2^(k+1) 的范围内进行二分查找。

另一种选择是执行相同的过程，直到第一个鸡蛋在 2^(k+1) 处破裂，然后重新开始，除了在每个高度上增加 2^k ： 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8，...。您可以一遍又一遍地重复此过程，以使指数搜索范围的大小不断缩小。

- Timothy Shields

---

如果提到“2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, ...”，则加1分。我认为这非常必要，因为在有界列表中，2^(k+1)很可能会“越界”。非常感谢，非常鼓舞人心。 - Rick