Re: Torre di Hanoi ricorsione

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

Ecco un'immagine d'esempio:

Immagine

Quello che non capisco è evidenziato. Sono proprio quelle chiamate ricorsive successive in cui cambiano sempre le variabili.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1746 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 19/06/2019, 17:01

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9732 di 10026
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 19/06/2019, 17:39

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?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1747 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 20/06/2019, 10:59

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9734 di 10026
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 20/06/2019, 12:54

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.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1748 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 20/06/2019, 14:07

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.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1749 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 21/06/2019, 09:01

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.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1750 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda vict85 » 21/06/2019, 10:50

È 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)
vict85
Moderatore
Moderatore
 
Messaggio: 9736 di 10026
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Torre di Hanoi ricorsione

Messaggioda ZfreS » 21/06/2019, 11:09

Ok, ma in questo caso perhè cambia così, quale sarebbe l'ordine delle chiamata ricorsive?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1751 di 1971
Iscritto il: 22/10/2016, 17:52

Re: Torre di Hanoi ricorsione

Messaggioda axpgn » 21/06/2019, 11:16

Quello scritto nel codice … :roll:
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 …
axpgn
Cannot live without
Cannot live without
 
Messaggio: 13716 di 14613
Iscritto il: 20/11/2013, 22:03

PrecedenteProssimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 9 ospiti