Torre di Hanoi ricorsione
Buongiorno! Sto studiando la torre di Hanoi e pur avendo capito il meccanismo che le sta dietro non riesco a capire il funzionamento del codice. Ho difficoltà a capire come funziona la ricorsione in questo problema. Ciò che non capisco dal codice è come fa l'algoritmo a spostare i dischi sul piolo b senza che b appaia nelle cout. Sembra che b sia un parametro che viene passato e non utilizzato, mentre poi compare nella stampa dei passaggi. Potreste farmi vedere passo dopo passo come opera la ricorsione con tre dischi? Grazie in anticipo!
void hanoi(int n, char a, char c, char b)
{
if (n == 1)
cout << a << " - " << c << endl;
else
{
hanoi(n - 1, a, b, c);
cout << a << " - " << c << endl;
hanoi(n - 1, b, c, a);
}
}
Risposte
Ok, supponendo di averne 3, faccio così: da A-C, A-B, C-B, A-C, B-A, B-C, A-C. Come vedi non cambio da B a C e da C a B.
Secondo te quella sarebbe una simulazione del funzionamento del programma ? 
"Simulazione" vuol dire eseguirlo passo passo ed ad OGNI SINGOLO passo verificare la situazione partendo dallo stato delle variabile e così via ...
Non c'è niente da fare, non hai la minima idea di cosa significhi fare le cose con metodo e attenzione ...
"Simulazione" vuol dire eseguirlo passo passo ed ad OGNI SINGOLO passo verificare la situazione partendo dallo stato delle variabile e così via ...
Non c'è niente da fare, non hai la minima idea di cosa significhi fare le cose con metodo e attenzione ...
Prima hanoi inzia con n=3 poi chiama se stessa ricorsivamente con n=2 e poicon n=1 dopodichè stampa A-C, ma se metto 4 dischi non stampa più A-C ma A-B anche se il codice direbbe il contario : cout << a << " - " << c << endl; Non mi è chiarissimo come funzioni la ricorsione doppia (perchè poi c'è di nuovo una chiamata ad hanoi)
Il fatto che hai scritto tre righe invece di una non cambia la situazione (oltre alla perla "anche se il codice direbbe il contrario : cout << a << " - " << c << endl;" )
Non devi scrivere qua quello che fai, devi metterti lì con calma, eseguire con calma ogni passo e ad ognuno di questi scrivere lo STATO delle cose, dal contenuto delle variabili al punto in cui ti trovi (che NON è banale perché quando chiami un'altra volta la stessa funzione ti ritrovi in un altro mondo, (quasi) del tutto nuovo, con NUOVE variabili anche se potrebbero avere lo stesso nome e ricordandoti che continua ad esistere la funzione "vecchia" (anzi LE funzioni) con le SUE variabili: per esempio con $n=4$ avrai QUATTRO funzioni aperte).
Devi metterti in testa (anche se lo so che è una causa persa) che i problemi NON sono così semplici come ti possono sembrare; anzi, anche quando il problema è semplice, la soluzione può essere tutt'altro che banale.
)Non devi scrivere qua quello che fai, devi metterti lì con calma, eseguire con calma ogni passo e ad ognuno di questi scrivere lo STATO delle cose, dal contenuto delle variabili al punto in cui ti trovi (che NON è banale perché quando chiami un'altra volta la stessa funzione ti ritrovi in un altro mondo, (quasi) del tutto nuovo, con NUOVE variabili anche se potrebbero avere lo stesso nome e ricordandoti che continua ad esistere la funzione "vecchia" (anzi LE funzioni) con le SUE variabili: per esempio con $n=4$ avrai QUATTRO funzioni aperte).
Devi metterti in testa (anche se lo so che è una causa persa) che i problemi NON sono così semplici come ti possono sembrare; anzi, anche quando il problema è semplice, la soluzione può essere tutt'altro che banale.
In effetti questo problema è parecchio complicato da capire sul lato della programmazione, da fare manualmente è facile.Tu hai detto che quando chiami un'altra volta la stessa funzione le variabili cambiano completamente, è qui che probabilmente mi blocco, ma perchè non so come quelle varibili cambiano. Capire il meccanismo della ricorsione nel caso del calcolo del fattoriale è facile, anche con altri esempi come l'ordinamento ma la torre di hanoi è un bagno di sangue!
La ricorsione usata da quel programma funziona come una pila. https://it.wikipedia.org/wiki/Pila_(informatica)
Quando fai una chiamata a quella funzione programmi di fare una azione, ma non la fai ancora (il push della pila). L'azione la fai quando stampi il risultato (il pop della pila). Nota infatti che ogni chiamata fa una sola stampa.
Quando fai una chiamata a quella funzione programmi di fare una azione, ma non la fai ancora (il push della pila). L'azione la fai quando stampi il risultato (il pop della pila). Nota infatti che ogni chiamata fa una sola stampa.
Non ho studiato ancora questa struttura dati, ma immagino che il pop sia il disco in cima che viene tolto. Ma una volta spostato il disco in cima sul piolo d'appoggio che in base al codice è C, il penultimo disco (osservando la torre dal basso all'alto) viene spostato dalla prima chiamata ricorsiva o dalla seconda (hanoi(n - 1, b, c, a);)?
Se provassi a farlo, manualmente, su carta, passo passo, come ti abbiamo già detto più volte, lo sapresti 
Lo avrei simulato su carta il codice se solo avessi capito come funziona. Dopo l'ultima chiamata ricorsiva della prima funzione: hanoi(n - 1, a, b, c); il programma passa al cout e poi alla seconda funzione che richiamera se stessa n-1 volte? Devo sapere se questo è vero prima di farlo su carta.
Ecco un'immagine d'esempio:
Quello che non capisco è evidenziato. Sono proprio quelle chiamate ricorsive successive in cui cambiano sempre le variabili.
Quello che non capisco è evidenziato. Sono proprio quelle chiamate ricorsive successive in cui cambiano sempre le variabili.
La logica del passaggio ricorsivo è la seguente:
Voglio spostare il disco di dimensione n dalla colonna A alla colonna C, ma non posso perché ho n-1 dischi sopra quello. Quindi prima di spostare questo disco in C, sposto i restanti dischi nella colonna di appoggio. A quel punto puoi spostare il disco di dimensione n nella colonna finale e rispostare gli altri dischi sopra quello (che ora si trovano nella colonna B). Questo ragionamento lo fai ricorsivamente. Nel codice si usano nomi discutibili per le variabili.
Voglio spostare il disco di dimensione n dalla colonna A alla colonna C, ma non posso perché ho n-1 dischi sopra quello. Quindi prima di spostare questo disco in C, sposto i restanti dischi nella colonna di appoggio. A quel punto puoi spostare il disco di dimensione n nella colonna finale e rispostare gli altri dischi sopra quello (che ora si trovano nella colonna B). Questo ragionamento lo fai ricorsivamente. Nel codice si usano nomi discutibili per le variabili.
Ok, il ragionamento mi è chiaro. Se devo spostare 3 dischi non posso perchè ne ho due e non posso ancora perchè ne ho uno ancora, ma una volta spostato quello, cosa succede? La chiamata a chi torna? Epoi prosegue col resto del codice o no?
Le domande che fai sono più di C++ che sull'algoritmo. Insomma, ogni chiamata a quella funzione (ad esclusione del caso n=1 che stampa e ritorna subito) fa tre cose: (1) chiama ricorsivamente se stessa, (2) stampa la propria azione, (3) chiama ricorsivamente se stessa. Fatto quello ritorna al proprio chiamante.
Ok vict, penso di essere sulla giusta strada per capire, sto facendo tutto l'algoritmo a mano e nel codice ho inserito delle cout che di volta in volta mi stampano i valori di A B e C.
Prima viene spostato il disco in cima e viene stampato A-C, poi la chiamata passa al secondo disco e viene stampato A-B. Ma dopo la chiamata deve andare a ritroso e passare al terzo disco, perchè invece ritorna al primo? Non mi è chiaro questo.
Forse non mi sono espresso chiaramente. All'inizio viene chiamta hanoi(3) che a sua volta chiama hanoi(2) che a sua volta chiama hanoi(1). Questa non avendo dischi al di sopra soddisfa il caso base della ricorsione e viene spostato da A a C. Ora, in base al meccanismo della ricorsione la chiamata torna ad hanoi(2) che è rimasta in attesa e poi compie il suo spostamento da A a B, ora mi aspetto che la chiamata torni ad hanoi(3) e invece torna ad hanoi(1). Questo fa si he le regole del gioco siano rispettate, ma stravolge il meccanismo della ricorsione che conosco. Vorrei capire la logica di questo.
È solo una ricorsione diversa, una ricorsione può chiamare se stessa un numero indeterminato di volte, e il numero può anche cambiare a seconda dagli input. Comunque non mi sembra sia un procedimento diverso dal QuickSort e in generale rientra negli algoritmi divide-et-impera. https://it.wikipedia.org/wiki/Divide_et ... nformatica)
Ok, ma in questo caso perhè cambia così, quale sarebbe l'ordine delle chiamata ricorsive?
Quello scritto nel codice …
Dopo l'else c'è una chiamata alla funzione col parametro $n-1$; quando torna ci sono ancora due righe di codice, no?
E quindi esegue quelle …
Una di esse è un'altra chiamata alla funzione con lo stesso parametro; quando ritorna anche da questa, dato che non ci sono più comandi da eseguire, ritorna alla funzione che l'ha chiamata …
Dopo l'else c'è una chiamata alla funzione col parametro $n-1$; quando torna ci sono ancora due righe di codice, no?
E quindi esegue quelle …
Una di esse è un'altra chiamata alla funzione con lo stesso parametro; quando ritorna anche da questa, dato che non ci sono più comandi da eseguire, ritorna alla funzione che l'ha chiamata …
Mi stai dicendo quindi che una volta spostato il disco in cima, vengono eseguitele istruzioni dell'else anzichè resistuire il controllo alla chiamata precedente?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo