Informatica · Algoritmi
Torre di Hanoi: dieci livelli
Da 1 a 10 dischi: gioca, osserva la ricorsione e prova a raggiungere il minimo di mosse.
Sposta tutti i dischi da A a C. Tocca un piolo per scegliere il disco superiore, poi tocca il piolo di arrivo. Puoi spostare un solo disco alla volta e non puoi appoggiare un disco grande su uno più piccolo. Anche tastiera: Tab per scegliere il piolo, Invio o Spazio per attivarlo.
Mosse eseguite—
Minimo dalla partenza—
Minimo ancora necessario—
Record manuale sul dispositivo—
Partita manuale
Avvia e Un passo continuano dalla posizione attuale: non devi ricominciare dopo una scelta diversa. Pausa lascia terminare la mossa già iniziata. Ricomincia azzera soltanto la partita corrente, non i record.
Il dispositivo non supporta l’animazione: le mosse restano disponibili passo passo.
Ultime mosse
- Nessuna mossa eseguita.
Sono mostrate le ultime 12 mosse; Annulla permette di risalire fino all’inizio della partita.
Livelli completati manualmente
I record manuali si salvano soltanto in questo browser, se disponibile. Nessun account o invio dei punteggi. Tutti i livelli sono già selezionabili.
Perché il minimo è 2ⁿ − 1?
Per spostare n dischi da A a C, prima libera il disco più grande: sposta i n−1 dischi sopra di lui su B. Poi sposta il disco n da A a C. Infine sposta i n−1 dischi da B a C.
- Sposta n−1 dischi da A a B, usando C come appoggio.
- Sposta il disco n da A a C.
- Sposta n−1 dischi da B a C, usando A come appoggio.
M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2n − 1
Il problema si ripresenta con un disco in meno: questa è la ricorsione. Con zero dischi non si fa nulla. Ogni disco aggiunto raddoppia il minimo precedente e aggiunge una mossa. Indizi e soluzione guidata usano la stessa strategia ricorsiva, adattata alla posizione attuale.
| Dischi | Minimo di mosse |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |