Бросание яиц из здания

Это упражнение задача 1.4.24 из 4-го издания алгоритмов Роберта Седжвика.

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?

Может ли кто-нибудь пролить свет на этот вопрос? Спасибо.
2 9
algorithm binary-search

2 ответа:

LogN: начинайте сверху, всегда сокращайте пространство поиска пополам - > бинарный поиск

2 * logF начните с 1, затем 2, 4, 8 (т. е., 2^i), как только яйцо разбивается (после шагов log F), выполните двоичный поиск в меньшем пространстве поиска (диапазон экспоненциальный Поиск

14

Решение 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, .... Вы можете продолжать повторять этот процесс, чтобы уменьшить размер диапазона, в котором выполняется экспоненциальный поиск.
4