Uova da lancio da un edificio

Questo è un problema di esercizio 1.4.24 di Robert Sedgewick's Algorithms 4th Edition.Uova da lancio da un edificio

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.

Mentre la soluzione lgN è facile pensare, ho assolutamente non hanno idea circa la soluzione 2lgF. Ad ogni modo, non viene fornito il valore di F, quindi dove si trova il terreno della soluzione 2lgF?

Qualcuno può dare un po 'di luce a questa domanda? Grazie.

fonte

2013-07-01 Guibao Wang

è un problema di ricerca dato un set ordinato. forse questo aiuta :). – Randy

Hay Randy, link o ulteriore lettura? –

Fare una ricerca binaria sull'edificio, scendere dal n/2 piano, se è rotto, quindi scendere che è n/4 e quindi uno. Quindi puoi rompere al massimo le uova di lgN e arrivare a quel punto nei passaggi lgN – Elbek

log N: avviare in alto, sempre tagliare spazio di ricerca a metà -> ricerca binaria

2 * logF iniziare a 1, il prossimo 2, 4, 8 (cioè, 2^I), una volta che l'uovo si rompe (dopo il log gradini F) fare ricerca binaria nello spazio di ricerca più piccolo (range < F, e quindi il numero di ricerche < log F) -> ricerca esponenziale

fonte

2013-07-01 12:39:56

Bella spiegazione, molto utile. @ Timothy: protegge anche la tua soluzione, grazie mille. –

E come si determina il valore di F? – Pavel

Non capisco come nella parte lgN otteniamo lgN uova rotte con lanci lgN, se continuiamo a dividere arriviamo al 1 ° piano alla fine, ma cosa succede se F = 7 e N = 8? non prendiamo le uova rotte lgN. Nella parte 2lgF non capisco come si ottengono anche uova rotte 2lgF, sembra che tu faccia solo 2lgF passaggi ma la tua quantità di uova rotte è 1. – Pavel

la soluzione è di fare lg(F)1, 2, 4, 8, ... fino al primo uovo si rompe a 2^(k+1) , quindi eseguire una ricerca binaria nell'intervallo 2^K a 2^(k+1).

Un'altra alternativa è quella di effettuare la stessa operazione fino ai primi uovo si rompe a 2^(k+1) poi ricominciare tranne aggiungendo 2^k ad ogni altezza: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... Puoi continuare a ripetere questo processo per ridurre le dimensioni dell'intervallo in cui esegui la ricerca esponenziale.

fonte

2013-07-01 12:41:21

Uova da lancio da un edificio

risposta

Problemi correlati