Torri di hanoi

di
matteo210
il
3 risposte
M
matteo210
Pochi posts
Iscritto da
gen, 2011
Messaggi:
7

Torri di hanoi

Ciao a tutti, mi sono appena iscritto al forum.
Sto imparando a programmare da autodidatta con l'ausilio di "C: corso completo di programmazione" di Deitel e Deitel. Sono arrivato agli esercizi del cap.5 senza grossi problemi (fino a qui li ho fatti tutti), ma ora, sull'esercizio sulle torri di Hanoi, che dovrebbe essere un modo semplice e intuitivo per introdurre le funzioni ricorsive, è da ieri che sbatto la testa contro il muro ma non riesco a venirne a capo.


In linea generale, teoricamente il problema dello spostare n dischi dal palo Inizio al palo Fine dovrebbere essere simile allo spostare n-1 dischi dal palo Inizio al palo Aux, dopodichè, spostando il disco n (cioè il più grosso) dal palo Inizio al palo Fine, e ripetendo il processo per spostare n-1 dischi da Aux a Fine, si giungerebbe alla soluzione del problema. Questa è la spiegazione che si trova anche sul libro e fino a qui mi sembra chiaro. Dopodichè però il libro da per scontato che a questo punto trovare un algoritmo sia un gioco da ragazzi, mentre io non riesco proprio a venirne a capo. Già tale situazione mi sembrava abbastanza imbarazzante, ma la mia frustrazione è aumentata quando ho trovato su internet il codice contenente il relativo argomento, e, nonostante il fatto che sia apparentemente semplicissimo, io non ci capisco niente lo stesso.

questo è il segmento rilevante del codice che ho trovato:

#include <stdio.h>


void muoviUnDisco(int sorgente, int destinazione)
{
printf(" muovi un disco da %2d a %2d\n", sorgente, destinazione);
} /* muoviUnDisco */


void muovi(int n, int sorgente, int destinazione, int ausiliario)
{
if (n == 1)
muoviUnDisco(sorgente, destinazione);
else {
muovi(n-1, sorgente, ausiliario, destinazione);
muoviUnDisco(sorgente, destinazione);
muovi(n - 1, ausiliario, destinazione, sorgente);
}
} /* muovi */

la funzione muovi segue esattamente la procedura sopra indicata, cioè per spostare n dischi da sorgente a destinazione tramite ausiliario, bisogna dapprima spostare n-1 da sorgente ad ausiliario, poi spostare n da sorgente a destinazione ed infine spostare n-1 da ausiliario a destinazione tramite sorgente. Ma se cerco di visualizzare o scrivere passo passo le operazioni che effettuerà il calcolatore, o arrivo ai passaggi sbagliati, o non riesco a seguirne la logica. Qualcuno potrebbe con pazienza indicarmi quindi passo passo le azioni che effettuerà il calcolatore seguendo il codice qua sopra? se ad es. n=3, ed ipotizzando sorgente=1, destinazione=3 e ausiliario=2, muovi(n-1, sorgente, ausiliario, destinazione) significa (2, 1, 2, 3). A questo punto si continua ricorsivamente con la stessa funzione muovi (ma perchè non si passa direttamente all'istruzione successiva?? nel blocco else non c'è un istruzione sul caso base n==1!), che diventerà (1, 1, 2, 3). A questo punto l'istruzione successiva stamperà muovi un disco da 1 a 3. Fino a qui è corretto? se si, cosa succede dopo??

Scusate la lunghezza ma sono veramente confuso e non so più cosa fare. E se penso che questa è la cosa più semplice da imparare, comincio a scoraggiarmi...aiutatemi per favore.

3 Risposte

  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Torri di hanoi

    Le funzioni ricorsive non sono così semplici da capire ma ci si riesce solo faccendo molti esercizi. Una funzione ricorsiva non conosce lo stadio precedente ed è questo che a te ti frega. Perche tu sai qual'è lo stato precedente. 
    
1. void muovi(int n, int sorgente, int destinazione, int ausiliario)
2. {
3. if (n == 1)
4. muoviUnDisco(sorgente, destinazione);
5. else {
6. muovi(n-1, sorgente, ausiliario, destinazione);
7. muoviUnDisco(sorgente, destinazione);
8. muovi(n - 1, ausiliario, destinazione, sorgente);
9. }
10. }
    Prendiamo in esame il tuo caso.
    n = 3, sorgente=1, destinazione=3 e ausiliario=2
    passo 1:
    siamo nel else: muovi(2, 1, 2, 3); //muovi 1 stage (riga nr.6)
    questo fa si che la prossima esecuzione sarà una nuovo funzione muovi e sarai sempre caduto nello stesso else: muovi(1, 1, 2, 3); //muovi 2 stage (riga nr.6)
    questo fa si che la prossima esecuzione sarà una nuovo funzione muovi e sarai caduto
    nel if: muoviUnDisco(1, 3); // muovi 3 stage (riga nr.4)
    adesso questo if finisce e ti posizioni nel muovi stage 2
    dentro l'else: muoviUnDisco(1, 3); //muovi 2 stage (riga nr.7)
    dentro l'else: muovi(1, 2, 3, 1); //muovi 2 stage (riga nr.8 )
    ecc fino ad uscire da tutta la trappola delle funzioni ricursive. Insomme te l'ho abbreviato un pò perche diventava lungo ma il procedimento dovresti averlo capito.
  • M
    matteo210
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    7

    Re: Torri di hanoi

    Grazie davvero skynet per l'aiuto. Dopo aver perso qualche altra ora a pensare, penso di aver finalmente tutto chiaro, e come al solito ora ciò che appariva complicatissimo sembra molto semplice, quasi banale.
    L'errore che facevo era, dalla seconda chiamata di fuzione in poi, considerare solo la prima istruzione (la funzione muovi) e non le altre 2.
    Ho scritto a penna uno schema con n=4 e ritorna tutte e 15 le istruzioni corrette. Riporto uno schema con n=3 per brevità, in caso potesse essere utile in futuro a qualcun altro che si trovi nella confusione in cui mi trovavo io.
    
supponendo n=3, s=1, d=3, a=2:
muovi (n,s,d,a):

se(n=1)
 stampa "muovi da s a d"

altrimenti:         ---muovi(n-2,s,d,a), n=1-> stampa "muovi da s a d"=muovi da 1 a 3 
 muovi(n-1,s,a,d)-------stampa"muovi da s a d" quindi "muovi da 1 a 2"
                    ---muovi(n-2,d,a,s), n=1-> stampa "muovi da s a d"=muovi da 3 a 2

 stampa "muovi da s a d"--stampa"muovi da 1 a 3"

                    ---muovi(n-2,a,s,d), n=1-> stampa "muovi da s a d"=muovi da 2 a 1
 muovi(n-1,a,d,s)-------stampa"muovi da s a d" quindi "muovi da 2 a 3"
                    ---muovi(n-2,s,d,a), n=1-> stampa "muovi da s a d"=muovi da 1 a 3
    in pratica la prima istruzione del'else inverte ogni volta i parametri 2 e 3 della funzione chiamante, mentre la terza istruzione dell'else inverte ogni volta i parametri 2 e 4 della funzione chiamante.

    Ho dovuto usare la tag code altrimenti non formattava correttamente lo schema.
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Torri di hanoi

    Anche se siamo nell'era dei computer il vecchio metodo di carta e penna non smentisce mai.
Devi accedere o registrarti per scrivere nel forum
3 risposte