Torre di hanoi

al_turing
Ciao ragazzi
mi aiutate a capire come funziona l'algoritmo ricorsivo della torre di hanoi?
ho trovato una montagna di informazioni in rete ma fin'ora ho visto solo spiegazioni troppo tecniche e incomprensibili per me da capire.
Magari spiegato con un linguaggio più malneabile potrei riuscire a capirci qualcosa.

GRAZIE MILLE!!!

Risposte
Cmax1
Ti allego di seguito l'estratto di una nota che avevo iniziato a scrivere, uh, un po' di anni fa. È rimasta solo abbozzata perché non si chiusero gli accordi con il committente. Te la propongo AS IT IS, spero possa esserti utile.

Se la piramide è formata da un solo disco, la soluzione è immediata:
muovere dal piolo sinistro a quello destro
Se invece la piramide è formata da N dischi,
spostare la piramide formata dagli N-1 dischi più piccoli dal piolo di sinistra a quello di centro, usando il piolo di destra come transito
muovere il disco dal piolo di sinistra [vi è rimasto il più grande] a quello di destra
spostare la piramide di N-1 dischi che ora si trova sul piolo di centro su quello di destra, usando il piolo di sinistra come transito
Si tratta della formulazione di un procedimento in termini del principio di induzione .
Non solo: non vi è alcun riferimento esplicito alla regola che impone di non impilare un disco su uno più piccolo.
Sembra quindi una formulazione solo più formale totalmente inutile dal punto di vista operativo, tuttavia, tradotta quasi letteralmente in un linguaggio ricorsivo, utilizzando un'adeguata struttura dati, per esempio una lista, fornisce direttamente la sequenza risolutiva di mosse.

Di seguito l'algoritmo implementato in Maple:

Hanoi(N, left, center, right) is
begin
    if N=1 then
        [left, right]
    else
        op([Hanoi(N-1, left, right, center)), 
        [left, right],
        op(Hanoi(N-1, center, left, right)])
    end if
end


L'istruzione op estrae l'operando da un'espressione, in questo caso, poiché stiamo trattando con liste del tipo [a,b], op([a,b]) = a,b, e serve semplicemente ad evitare l'annidamento delle liste, del tipo [a,[b,c]].
Esempio:

Hanoi(4, sinistra, centro, destra)

[destra, centro], [destra, sinistra], [centro, sinistra],
[destra, centro], [sinistra, destra], [sinistra, centro],
[destra, centro], [destra, sinistra], [centro, sinistra],
[centro, destra], [sinistra, destra], [centro, sinistra],
[destra, centro], [destra, sinistra], [centro, sinistra]


PS. Qualsiasi riferimento a passaggi di schieramento di personaggi politici italiani è puramente casuale.

milizia96
Il succo del discorso è questo:
Spostare $N>0$ dischi dal paletto $A$ al paletto $C$ equivale a:
1) Spostare $N-1$ (cioè tutti tranne il più grande) dischi da $A$ a $B$;
2) Spostare il disco rimasto da $A$ a $C$;
3) Spostare gli $N-1$ dischi da $B$ a $C$.
Questa procedura richiama se stessa tante volte, finché non si raggiunge $N=0$ che non fa eseguire nessuna istruzione.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.