从建筑物扔鸡蛋

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),一旦蛋中断(在日志F步骤之后)在较小的搜索空间中进行二分搜索(范围<F,因此搜索次数<log F) - >指数搜索

Answer 2

该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, ....您可以继续重复此过程,以减少指数搜索范围的大小.