Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 19/06/2019, 10:05

Ieri non mi ero focalizzato abbastanza, hai ragione, la logica è lì. Semplicemente la prima azione è dopo varie chiamate ricorsive. Comunque, per capire perché nel caso pari devi partire mandando il più piccolo in 'b' ti suggerisco di cercarti una versione giocabile del gioco di Hanoi (ci saranno giochi javascript o flash gratuiti immagino). Con 4 il numero di mosse non è altissimo.
vict85
Moderatore
Moderatore
 
Messaggio: 9727 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 19/06/2019, 10:15

@Zfres
Non conosco il linguaggio in questione (e neppure programmo :D ) però se noti chiama la funzione con $a, c, b$ non $a, b, c$.
Se $n=1$ mette $a$ su $c$, altrimenti richiama la funzione (diminuendo $n$) ma con $b$ e $c$ scambiati quindi, per esempio nel caso $n=2$ la seconda chiamata fa mettere $a$ su $b$.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13689 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 10:20

Ok, noi possiamo ragionare così. Ma nel codice c'è scritto che il disco in cima alla torre andrà spostato su B, non specifica se il numero di dischi è pari o dispari. E' una cosa che decide il compilatore? Una volta spostato il primo disco, la funzione a chi viene passata?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1736 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 10:22

Si axpgn quello l'ho notato se metto 2 dischi quello in cima lo mette su B. Ma se ne metto 3 o 5 quello in cima lo mette su C. Sto cercando di capire se è una decisione che prende il compilatore in base alla parità dei dischi, perchè nel codice questo non è specificato pe cui a prescindere dalla parità il disco in cima andrebbe messo su B.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1737 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 19/06/2019, 10:32

C'è, ma è nascosto. Nella prima chiamata ricorsiva si limita a scambiare b e c. Se tu ripeti due volte questa operazione, la annulli tornando allo stato di partenza. Quindi, siccome questa chiamata si ripete \(n-1\) volte, capirai che per n dispari, b e c non vengono scambiati, mentre per n pari lo sono.
vict85
Moderatore
Moderatore
 
Messaggio: 9728 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 10:43

Ma come fa a scambiare B e C senza stamparlo? Quando viene chiamata hanoi, con 3 dischi viene richiamata co 2 e poi con 1 e quindi stampa A-C ma nel frattempo come dici tu ha fatto (A-B,C-B, B-C) senza stamparlo?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1738 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 19/06/2019, 11:01

Cosa hai scritto nel titolo? "Ricorsione"
Ecco, riflettici …

Se $n=1$ la prima parte dell'if viene eseguita, altrimenti (cioè se $n>1$) viene chiamata la funzione $n-1$ volte, finché non viene eseguita la prima parte (e quindi vengono scambiati $b$ e $c$, $n-1$ volte.
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13690 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 11:08

Si su questo ci sono, ma allora dovrebbe anche stamparlo a schermo o no?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1739 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 19/06/2019, 11:19

Perché? Il programma, dopo l'else, non fa che chiamare, RICORSIVAMENTE, la funzione finche $n$ non diventa $1$.
A quel punto esegue la prima parte dell'if e POI torna da dove è stata chiamata.
Quindi se $n=100$, il programma chiama novantanove volte la funzione (e ovviamente scoppia prima :wink:) prima di stampare qualcosa.
Si chiama "ricorsione" per questo.
Comunque segui il consiglio di vict85, simula quello che fa il programma con $n=4$ e osserva ...
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13691 di 40641
Iscritto il: 20/11/2013, 22:03

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 11:32

Si ho osseravato un'animazione, ma una volta che torna dove è stata chiamata cosa succede? Va avanti stampando con il cout, poi chiama di nuvo ricorsivamente se stessa nell'ordine in cui è scritto il codice?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1740 di 4589
Iscritto il: 22/10/2016, 17:52

PrecedenteProssimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite