Due marmi e un edificio di 100 piani

https://stackoverflow.com/questions/6547

08-06-2019
|

Domanda

Una di quelle classiche domande da intervista di programmazione...

Ti vengono date due biglie e ti viene detto che si romperanno se lasciate cadere da una certa altezza (e presumibilmente non subiranno danni se lasciate cadere da sotto quell'altezza).Verrai quindi portato in un edificio di 100 piani (presumibilmente più alto di una certa altezza) e ti verrà chiesto di trovare il piano più alto da cui puoi far cadere una biglia senza romperla nel modo più efficiente possibile.

Informazioni aggiuntive

Devi trovare il piano corretto (non un intervallo possibile)
È garantito che le biglie si rompano entrambe sullo stesso piano
Supponiamo che non ci voglia tempo per cambiare piano: conta solo il numero di gocce di marmo
Supponiamo che il piano corretto sia distribuito casualmente nell'edificio

Soluzione

La cosa interessante qui è come puoi farlo nel minor numero di gocce possibile.Andare al 50° piano e lasciar cadere il primo sarebbe disastroso se il piano che si rompe fosse il 49°, con il risultato che dovremmo fare 50 cadute.Dovremmo far cadere la prima biglia al piano n, dove n è la quantità massima di gocce richieste.Se la biglia si rompe al piano n, potremmo dover fare n-1 gocce successivamente.Se la biglia non si rompe saliamo al piano 2n-1 e se si rompe qui dobbiamo far cadere la seconda biglia n-2 volte nel peggiore dei casi.Continuiamo così fino al 100° piano e proviamo a romperlo a 3n-2, 4n-3....
e n+(n-1)+(n-2)+...1 <=100
n=14 È la caduta massima richiesta

Altri suggerimenti

Questo problema è trattato nel Problema 6.5 dal Libro "Cracking the Coding Intervista (5°)", con soluzioni così riassunte:

Osservazione:

Indipendentemente da come tralasciamo Marble1, Marble2 deve eseguire una ricerca lineare.Ad esempio, se il marmo1 si rompe tra il pavimento 10 e 15, dobbiamo controllare ogni piano tra il marmo2

L'approccio:

Un primo tentativo: Supponiamo di far cadere una biglia dal 10° piano, poi dal 20°,...

Nella prima biglia si rompe alla prima caduta (piano 10), quindi avremo al massimo 10 gocce in totale.
Se il primo marmo si rompe sull'ultima goccia (piano 100), allora abbiamo al massimo 19 gocce in totale (piano da 1 a 100, quindi da 91 a 99).
È abbastanza buono, ma tutto ciò che consideriamo è il caso peggiore in assoluto.Dovremmo fare un po 'di "bilanciamento del carico" per rendere più pari questi due casi.

Obiettivo: Crea un sistema per far cadere Marble1 in modo che il numero massimo di gocce richiesto sia coerente, indipendentemente dal fatto che Marble1 si rompa alla prima o all'ultima goccia.

Un sistema bilanciato perfettamente carico sarebbe uno in cui le gocce di marmo1 + gocce di marmo2 sono sempre le stesse, indipendentemente da dove si è rotto il marmo1.
Per questo, poiché ogni goccia di Marble1 fa un altro passo, Marble2 è consentito un passo in meno.
Pertanto, dobbiamo ridurre il numero di passaggi potenzialmente richiesti da Marble2 di un calo ogni volta.Ad esempio, se Marble1 viene lasciato cadere sul pavimento 20 e quindi il pavimento 30, Marble2 è potenzialmente richiesto per fare 9 passi.Quando rilasciamo nuovamente Marble1, dobbiamo ridurre i potenziali passaggi di Marble2 a soli 8.ad esempio, dobbiamo rilasciare Marble1 al piano 39.
Sappiamo, quindi, Marble1 deve iniziare dal pavimento X, quindi salire dai piani X-1, quindi X-2, ..., fino a quando non arriva a 100.
Risolvi per X+(X-1)+(X-2)+…+1 = 100.X(X+1)/2 = 100 -> X = 14

Andiamo al piano 14, poi 27, poi 39,... Ci vogliono al massimo 14 gradini.

Codice ed estensione:

Per l'implementazione del codice, puoi controllare Qui.
Per l'estensione a N marmi, M pavimenti, controlla Capitolo 12:Il puzzle delle uova e dei pavimenti .

Si rompono se lasciati cadere dalla stessa altezza o sono diversi?

Se sono uguali, vado al cinquantesimo piano e lascio cadere la prima biglia.Se non si rompe vado al 75° piano e faccio lo stesso, finché non si rompe continuo a salire del 50% di quello che resta.Quando si rompe, torno a quello più in alto rispetto a dove ero prima (quindi se si rompe al 75° piano torno al 51° piano) e lascio cadere la seconda biglia e salgo di un piano alla volta finché non si rompe, a quel punto conosco il piano più alto da cui posso cadere senza che il marmo si rompa.

Probabilmente non è la risposta migliore, sono curioso di vedere come rispondono gli altri.

Lascia cadere la prima biglia al piano 10, 20, 30, ecc.finché non si rompe, poi torna all'ultimo conosciuto Bene pavimento e inizia a far cadere le biglie da lì un piano alla volta.Il caso peggiore è che 99 sia il Magic Floor e puoi sempre trovarlo in 19 gocce o meno.

Personalmente non sono un grande fan di questi enigmi, preferisco veri e propri esercizi di programmazione nelle interviste.

Detto questo, in primo luogo dipenderebbe dal fatto se riesco a capire se sono rotti o meno dal pavimento su cui li sto lasciando cadere.Presumo di poterlo fare.

Salivo al secondo piano e lasciavo cadere la prima biglia.Se si rompesse proverei il primo piano.Se si rompesse, saprei che non c'era il pavimento.

Se il primo non si rompesse, andrei al 4° piano e cadrei da lì.Se si rompesse, tornerei giù e prenderei l'altra biglia, poi cadrei al 3 ° piano, rompendo o no, saprei qual è il limite.

Se nessuno dei due si rompesse, andrei a prenderli entrambi e farei lo stesso processo, questa volta iniziando dal 6° piano.

In questo modo posso saltare ogni altro piano finché non ottengo una biglia che si rompe.

Questo sarebbe ottimizzato se il marmo si rompe presto...Suppongo che probabilmente ci sia un numero ottimale di piani che potrei saltare per ottenere il massimo da ogni salto...ma se poi se ne rompe uno, dovrei controllare ogni piano individualmente dal primo piano sopra l'ultimo piano conosciuto...il che ovviamente sarebbe una seccatura se saltassi troppi piani (mi spiace, non troverò la soluzione ottimale in questo momento).

Idealmente, vorrei un intero sacco di biglie, poi potrei usare un algoritmo di ricerca binaria e dividere il numero di piani a metà con ogni goccia...ma allora la domanda non era quella, no?

Penso che la vero la domanda è quanto precisa vuoi la risposta.Perché la tua efficienza dipenderà davvero da questo.

Sono d'accordo con Justin se vuoi una precisione al 100% sui marmi, una volta che il primo marmo si rompe, dovrai salire 1 piano alla volta dall'ultimo pavimento "buono" noto fino a quando non scopri quale piano è il vincitore." Forse anche lanciare alcune statistiche e iniziare al 25 ° piano invece del 50 ° piano in modo che lo scenario peggiore sarebbe 24 anziché 49.

Se la tua risposta può essere più o meno un piano o due, potrebbero esserci delle ottimizzazioni.

In secondo luogo, salire e scendere le scale influisce sulla tua efficienza?In tal caso, lascia sempre cadere entrambe le biglie e raccoglile entrambe durante ogni viaggio su/giù.

Lascia cadere la prima biglia dal 3° piano.Se si rompe, sai che è il piano 1 o 2, quindi lascia cadere l'altra biglia dal piano 2.Se non si rompe hai scoperto che il piano 2 è il più alto.Se si rompe, hai scoperto che il piano 1 è il più alto.2 gocce.

Se cadere dal 3° piano non rompe la biglia, lanciati dal piano 6.Se si rompe, sai che il piano 4 o 5 è il più alto.Lascia cadere la seconda biglia dal piano 5.Se non si rompe hai scoperto che 5 è il massimo.In tal caso, il piano 4 è il più alto.4 gocce.

Continua.

3 piani - massimo 2 cadute

6 piani - massimo 4 cadute

9 piani - massimo 6 cadute

12 piani - massimo 8 cadute

eccetera.

3 piani - massimo 2 cadute

Quindi per un edificio di 99 piani avresti un massimo di 66 cadute.E questo è il massimo.Probabilmente avresti meno gocce di così.Oh, e 66 è anche il massimo per un edificio di 100 piani.Avresti bisogno solo di 66 gocce se il break floor fosse il 98 o il 97.Se il break floor fosse 100 utilizzeresti 34 gocce.

Anche se hai detto che non importa, questo probabilmente richiederebbe una minima camminata e non è necessario sapere quanto è alto l'edificio.

Parte del problema è come definisci l’efficienza.È più "efficiente" avere sempre una soluzione in meno di x gocce, oppure è più efficiente avere buone possibilità di avere una soluzione in y gocce dove y < x con l'avvertenza che potresti avere più di x gocce ?

Questo può essere fatto meglio con solo 7 biglie.

Quindi, seguendo la risposta votata, diciamo che il marmo si rompe almeno al 49esimo piano.

50° piano -> pause (la risposta è compresa tra 1 e 50 inclusi)
25° piano -> non si rompe (da 26 a 50)
37° piano -> non si rompe (da 38 a 50)
43° piano -> non si rompe (da 44 a 50)
46° piano -> non si rompe (da 47 a 50)
48° piano -> non si rompe (49 o 50)
49° piano -> rotture (49°, questo passaggio è effettivamente necessario perché potrebbe essere stato il piano minimo per la rottura del marmo è al 50°)

Questo può essere immaginato come eseguire una ricerca binaria in un insieme ordinato per qualche k, dove dimezziamo lo spazio della soluzione ad ogni tentativo.Per 100 piani abbiamo bisogno di log2 100 = 6.644 (7 tentativi).Con 7 biglie possiamo essere sicuri qual è il piano minimo che la biglia romperà fino a 128 piani.

La prima cosa che farei è utilizzare il semplicissimo algoritmo che inizia dal piano 1 e fa cadere la biglia un piano alla volta finché non raggiunge 100 o la biglia si rompe.

Quindi mi chiederei perché dovrei dedicare del tempo a ottimizzarlo finché qualcuno non può dimostrare che sarà un problema.Troppe volte le persone si concentrano sulla ricerca dell'algoritmo complicato perfetto quando uno molto più semplice risolverà il problema.In altre parole, non ottimizzare le cose finché non è necessario.

Questa potrebbe essere una domanda trabocchetto per vedere se sei una di quelle persone che riescono a trasformare una talpa in una montagna.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow