[C] Torri di Hanoi

[noodles]

Sto impazzendo ; allora devo creare una funzione ricorsiva che prende in input il numero di dischi, la torre di partenza, quella di appoggio e quella di arrivo. Questa funzione deve stampare le mosse per risolvere il problema delle torri...
Le funzioni ricorsive le ha capite abbastanza, ma ho capito quelle che restituiscono un numero (per esempio il fattoriale di un numero), ma questa proprio non ci arrivo.
Allora supponiamo di avere una torre con 3 dischi nel primo palo, che devono essere spostati nel terzo palo:
hanoi(3)
richiamo hanoi(2) e in seguito stampo(1 --> 3, cioè sposto il terzo disco dal primo palo al terzo)
hanoi(2)
richiamo hanoi(1) e in seguito stampo(1 --> 2)
hanoi(1) stampa(1 --> 3)

piu' o meno la ricorsione dovrebbe essere cosi'??

Mi ci fate arrivare in qualche modo???






Sto impazzendo di giorno in giorno (se uno si sforza troppo si rischia di impazzire??? )


grazie

[noodles]

quando mi ricapita di avere a che fare con le funzioni ricorsive, è meglio partire dall'"alto" o dal "basso"?? Analizzo prima il caso di base???



grazie

[recoil]

se vuoi un consiglio il modo migliore per capire come funziona la ricorsione è vederla in assembly oppure studiarsi per bene come funzionano il record di attivazione delle funzioni e lo stack.

se il tuo problema invece è capire quando o come usare una funzione ricorsiva allora non saprei come dirti. per me la ricorsione spesso è la soluzione più intuitiva mentre è più complesso il ragionamento per arrivare ad una soluzione iterativa.

[noodles]

nessuno sa darmi una mano???

[goldorak]

Ciao, la soluzione e' abbastanza semplice. Supponi di spostare n ( n >=1) dischi dal piolo a al piolo c utilizzando il piolo b come piolo ausiliario. Sia Hanoi(n,a,b,c) la funzione che ti stampa l'elenco delle mosse da fare. Inanzitutto devi identificare il caso base ed il caso passo. Il caso base consiste nel spostare 1 disco dal piolo a al piolo c quindi basta stampare a->c. Per il caso passo invece devi spostare n dischi dal piolo a al piolo c. Quindi prima sposti n-1 dischi dal piolo a al piolo b utilizzando il piolo c come piolo ausiliario. Poi ti rimane 1 disco da spostare dal piolo a al piolo c. Come ultimo passo sposti gli n-1 dischi dal piolo b al piolo c utilizzando il piolo a come piolo ausiliario. In pseudo codice la funzione e'

Hanoi(n,a,b,c) { //sposta n dischi dal piolo a al piolo c tramite il piolo b
 if n=1 then stampa a->c
 else { Hanoi(n-1,a,c,b)
            stampo a->c
           Hanoi(n-1,b,a,c)}
}

[noodles]

Capito. Grazie mille