Torre di Hanoi ricorsione

Messaggioda ZfreS » 18/06/2019, 14:40

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!
Codice:
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);
   }
}
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1730 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 18/06/2019, 15:45

Seppur l'algoritmo sia ben conosciuto, l'implementazione e, soprattutto, il modo di presentare il risultato non è certo unico. Immagino che la presentazione del risultato sia del tipo "1 - 2" con il significato di "sposto l'elemento più alto della colonna 1 nella colonna 2", giusto? Tra l'altro immagino che ci sia una funzione esterna che chiama la versione giusta a seconda della parità di n.

Comunque non capisco il tuo dubbio: i tre caratteri non hanno lo stesso ordine in tutte le chiamate.
vict85
Moderatore
Moderatore
 
Messaggio: 9721 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 18/06/2019, 15:51

a indica il primo piolo da cui si inizia, b indica il piolo d'appoggio e c indica il piolo su cui andranno spostati tutti i dischi alla fine. Non ci sono varianti e casi particolari che dipendano dalla parità di n. Quel che non capisco e l'odine di esecuzione delle chiamate ricorsive. Potresti gentilmente elencarmeli per farmi capire cosa succede ad ogni chiamata, supponendo di vare 3 dischi?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1731 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 18/06/2019, 16:18

Se vuoi vedere l'ordine delle chiamate ricorsive non ti servo io, è sufficiente aggiungere un cout come prima riga dalla funzione.
vict85
Moderatore
Moderatore
 
Messaggio: 9723 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 18/06/2019, 16:20

Cosa devo inserire però nella cout? Mi serve vedere l'ordine per capire questo: il caso base della ricorsione consiste nel spostare il disco da A a C, ma in realtà viene spostato su B. Ma nel codice mica c'è scritto che si deve spostare prima su B e poi su C. So che forse è una stupidaggine, ma non sto capendo questo.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1732 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 18/06/2019, 16:34

L'algoritmo è incompleto, manca infatti il primo passo. Questo comunque è la soluzione minimale per il caso n=3
1)
Codice:
1  |  |
2  |  |
3  |  |

2)
Codice:
|  |  |
2  |  |
3  |  1

3)
Codice:
|  |  |
|  |  |
3  2  1

4)
Codice:
|  |  |
|  1  |
3  2  |

5)
Codice:
|  |  |
|  1  |
|  2  3

6)
Codice:
|  |  |
|  |  |
1  2  3

7)
Codice:
|  |  |
|  |  2
1  |  3

8)
Codice:
|  |  1
|  |  2
|  |  3
vict85
Moderatore
Moderatore
 
Messaggio: 9725 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 18/06/2019, 16:43

Scusa Vict, quel passo manca? A me come prima mossa stampa da A a C se metto 3 dischi ma se ne metto 4 mi da come prima mossa da A a B. Non capisco come fa l'algoritmo a sfruttare il piolo B e decidere se mettere il primo disco su B o su C. Lo fa dalla seconda chiamata ricorsiva(dopo il cout) ?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1733 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 18/06/2019, 17:18

Beh, su quale piolo metterlo è semplice: se il piolo di arrivo deve essere sempre C allora il primo spostamento deve essere su C se i dischi sono in numero dispari, deve essere su B se sono pari.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13687 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 18/06/2019, 17:23

Ah bene, ma questo è un meccanismo mascherato allora, perchè il codice è molto snello ma di fatto fa molto!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1734 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 09:29

Cerchiamo di capire bene cosa succede: la prima esecuzione di hanoi passa a chiamre hanoi stessa perchè abbiamo 3 dischi e non 1, a questo punto hanoi richiamera se stessa con 2 dischi e poi di nuovo se stessa con 1 disco che sposterà da A a C, poi viene eseguita la cout tra le due hanoi e in seguito viene eseguita l'ultima hanoi ricorsivamente. Sono sicuro che non sia questo l'ordine delle chiamate ricorsive per qusto ti chiedevo di scrivermelo. In teoria il disco in cima dovrebbe essere spostato su B perchè nella prima chiamata ricorsiva è il piolo B ad essere quello di fine mentre il piolo C è d'appoggio e provando con 4 dischi in effetti la prima mossa e A-B e non A-C, mentre con tre dischi la prima mossa dovrebbe essere A-B in base a questa istruzione: hanoi(n - 1, a, b, c); ma in realtà è A-C. Vorrei capire bene il perchè di questo.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1735 di 4589
Iscritto il: 22/10/2016, 17:52

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite