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?!

[sayian]

Nella mia breve esperienza di ottimizzazione di algoritmi, di solito ho constatato che le versioni iterative sono sensibilmente più lente e meno efficiente rispetto a quelle ricorsive. Che io sappia, l'unico handicap degli algoritmi ricorsivi è il limite di memoria dello stack.

[tasso85]

Nella mia breve esperienza di ottimizzazione di algoritmi, di solito ho constatato che le versioni iterative sono sensibilmente più lente e meno efficiente rispetto a quelle ricorsive. Che io sappia, l'unico handicap degli algoritmi ricorsivi è il limite di memoria dello stack.

eh no eh! aggiungi tutto il lavoro per creare i vari recordi di attivazione, allocare la memoria, ecc ecc... quello che ottieni è che l'algoritmo ricorsivo è generalmente più lento ma MOLTO più facile da scrivere

io avevo provato con un semplice algortimo per la serie di Fibonacci.. ricorsivo, era lentino, già a valori non enormi ci metteva parecchio... iterativo, una scheggia