Torre di Hanoi
Da Wikipedia, l'enciclopedia libera.
La Torre di Hanoi è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.
Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti dischi sull'ultimo paletto, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.
Indice |
[modifica] Origini
Il gioco fu inventato dal matematico francese Edouard Lucas nel 1883. Una leggenda, non si sa se reale o inventata dal matematico, parla di un tempio Indù dove alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d'oro secondo le regole della Torre di Hanoi (a volte chiamata Torre di Brahma). La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà.
[modifica] Soluzione
La proprietà matematica base è che il numero minimo di mosse necessarie per completare il gioco è 2n - 1, dove n è il numero di dischi. Ad esempio avendo 3 dischi, il numero di mosse minime è 7. Di conseguenza, secondo la leggenda, i monaci di Hanoi dovrebbero effettuare almeno 18.446.744.073.709.551.615 mosse prima che il mondo finisca, essendo n = 64.
La soluzione generale è data dall'algoritmo seguente.
[modifica] Algoritmo ricorsivo
- Si etichettano i paletti con le lettere A, B e C
- Dato n il numero dei dischi
- Si numerano i dischi da 1 (il più piccolo, in alto) a n (il più grande, in basso)
Per spostare i dischi dal paletto A al paletto B:
- Sposta i primi n-1 dischi da A a C. Questo lascia il disco n da solo sul paletto A
- Sposta il disco n da A a B
- Sposta n-1 dischi da C a B
Questo è un algoritmo ricorsivo, di complessità esponenziale, quindi per risolvere il gioco con un numero n di dischi, bisogna applicare l'algoritmo prima a n-1 dischi. Dato che la procedura ha un numero finito di passi, in un qualche punto dell'algoritmo n sarà uguale a 1. Quando n è uguale a 1, la soluzione è banale: basta spostare il disco da A a B.
[modifica] Altri progetti
Commons contiene file multimediali su Torre di Hanoi
[modifica] Collegamenti esterni
