Un Simpatico Algoritmo!, la torre di Hanoi Opzioni

[pottydj]

Esercizio: Torre di Hanoi
Siano dati 3 pioli verticali, numerari da 0 a 2, ed un numero n di dischi di dimensioni decrescenti.
All’inizio del gioco i dischi sono tutti impilati in ordine di grandezza decrescente, dal basso verso l’alto, sul
primo piolo.
L’obiettivo del gioco è quello di spostare tutti i dischi dal piolo 0 al piolo 1 rispettando le seguenti regole:
1. è possibile spostare un solo disco alla volta
2. un disco non può essere impilato su un altro disco di dimensioni più piccole
NOTA: Il piolo 2 è usato come piolo di supporto durante i trasferimenti.

Il seguente algoritmo risolve il problema osservando che, l’unico modo per spostare il disco più grande dal
piolo 0 al piolo 1 consiste nello spostare prima tutti gli altri dischi sul piolo 2. Quindi:
1. sposta i primi n − 1 dischi dal piolo 0 al piolo 2, rispettando la legge
2. sposta l’ultimo disco dal piolo 0 al piolo 1
3. sposta i primi n − 1 dischi dal piolo 2 al piolo 1
I punti 1 e 3 implicano la risoluzione del problema di dimensione n − 1 con una permutazione dei nomi dei
pioli (al secondo passo il piolo 0 diviene il piolo di supporto).

CODICE

//Utilizzando il tipo di dato pila per definire un piolo, la procedura specifica in precedenza per la risoluzione del problema può essere così codificata:

void torredihanoi ( int n, piolo origine, piolo destinazione, piolo intermedio ) {
if ( n == 1 ) {
muovidisco ( origine , destinazione );
} else {
torredihanoi ( n − 1 , origine , intermedio , destinazione ); //RICORSIONE!!
muovidisco ( origine , destinazione );
torredihanoi ( n − 1 , intermedio , destinazione , origine ); //RICORSIONE!!
}
}


La procedure muovidisco deve:
1. leggere l’elemento di testa dal piolo origine (LEGGIPILA) e scriverlo in testa al piolo destinazione
(SCRIVIPILA)
2. cancellare l’elemento di testa del piolo origine (CANCPILA)

in pratica questo algoritmo varia esponenzialmente! Se si usano anche solo 18 dischi di dimensione crescente (che poi nell'impelementazione sono semplicemente dei valori interi crescenti) il tempo di calcolo (costo computazionale) equivale ad 1 giorno!! con 31-32 si passa già ad un secolo... affascinante!! Che ne dite?!

[cj@cc.gatech.edu]

C'era anche in Ultima VIII... chi di voi l'ha finito... c'è passato :\