algorithm - 从建筑物中扔鸡蛋

Question

这是 Robert Sedgewick 的算法第 4 版中的练习题 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解决的依据在哪里？

任何人都可以对这个问题有所了解吗？谢谢。

Answer 1

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

2 * logF 从 1 开始，接下来是 2、4、8（即 2^i），一旦鸡蛋破裂（在 log F 步之后）在较小的搜索空间中进行二分搜索（范围 < F，因此搜索次数 < log F) --> 指数搜索

Answer 2

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

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