Rzucanie jajkami z budynku

Question

To jest problem z ćwiczeniem 1.4.24 z Algorytmów Roberta Sedgewicka w wydaniu czwartym.

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. 

Choć rozwiązanie lgN jest łatwo wymyślić, ja zupełnie nie mają pojęcia o rozwiązaniu 2lgF. W każdym razie nie podajemy wartości F, więc gdzie jest podstawa rozwiązania 2lgF?

Czy ktoś może dać trochę światła na to pytanie? Dzięki.

Answer 1

logN: zaczynają się góry, zawsze wyciąć przestrzeni poszukiwań w połowie -> Wyszukiwanie binarne

2 * logF zaczynają się od 1, następna 2, 4, 8 (czyli 2^I) po przerwach jaj (po zalogowaniu kroki f) wykonać przeszukiwanie binarne w mniejszej przestrzeni poszukiwań (zakres < F, a tym samym liczbę wyszukiwań < log F) -> wyszukiwanie wykładniczy

Answer 2

rozwiązanie lg(F) jest zrobić 1, 2, 4, 8, ... do pierwszych przerw jaj w 2^(k+1) , a następnie wykonaj wyszukiwanie binarne w zakresie od 2^K do 2^(k+1).

Inną alternatywą jest przeprowadzenie tego samego procesu, aż do momentu pierwszego rozbicia jajka pod numerem 2^(k+1), a następnie rozpoczęcia od nowa z wyjątkiem dodania 2^k do każdej wysokości: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... Możesz kontynuować powtarzanie tego procesu, aby zmniejszyć rozmiar zakresu wyszukiwania wykładniczego.