RISOLTO Problema con torre di hanoi

[olegfresi]

Buongiorno! Sto studiando la torre di hanoi con l'implementazione ricorsiva, ma non riesco a capirne il funzionamento. Ho capito come funziona il gioco, so come risolverlo manualmente ma non capisco come fa il codice ad effettuare certi passaggi. Uso il c++. Il codice è il seguente:

void t_hanoi(int dischi, char part, char arr, char app)
{
   if (dischi == 1)
      cout << part << " - " << arr << endl;
   else
   {
      t_hanoi(dischi - 1, part, app, arr);
      cout << part << " - " << arr << endl;
      t_hanoi(dischi - 1, app, arr, part);
   }
}

part: piolo di partenza
app: piolo di appoggio
arr: piolo di arrivo

Provo a spiegare il funzionamento del codice fino al punto del mio dubbio: la funzione t_hanoi viene chiamata nel main con questi parametri: 3, A, C, B. Le lettere indicano i vari pioli. Il piolo di partenza A ha 3 dischi. Una volta chiamata la funzione entra in gioco la if che fallisce dato che i dischi sono 3, quindi si passa a richiamare la funzione nella prima riga dell'else, che chiama t_hanoi con i parametri: 2, A, B, C dopodichè si ripete la if che fallisce poichè ci sono ancora 2 dischi e la funzione richiama se stessa nella prima riga dell'else con i parametri: 1, A, C, B. A questo punto si ripete la if che va a buon fine poichè c'è un disco solo e stampa come prima mossa: A-C. Ora arriva i bello: il programma, invece di andare a ritroso per recuperare le chiamata precedenti lasciate in sospeso sembra che proceda con le altre istruzioni dell'else (non so se salta o no la prima riga). Vorrei che mi spiegaste perchè ciò accade e come dovrebbe continuare dal punto in cui mi sono fermato. vi chiedo questo principalmente perchè non so in che ordine avvengono le altre istruzioni. Pensavo che questo funzionasse come la versione ricorsiva del fattoriale ovvero una volta raggiunto il caso base, si andava a ritroso fino alla prima chiamata che restituiva il risultato. Potrste aiutarmi a capireper favore? Vi ringrazio in anticipo!

 

[fabio93]

t_hanoi e hanoi sono funzioni diverse?

 

[olegfresi]

No, ho sbagliato io. Correggo subito.

 

[fabio93]

Non c'è alcuna anomalia nelle chiamate ricorsive: dopo la chiamata con i parametri 1, A, C, B, in cui viene eseguita l'istruzione nel ramo if, che stampa A - C, il controllo ritorna al chiamante (a sua volta invocato con i parametri 2, A, B, C), cioè subito dopo la prima istruzione nel ramo else. Quindi viene eseguita la seconda istruzione nel ramo else, che stampa A - B, dopodiché viene effettuata la chiamata ricorsiva (terza istruzione) con i parametri 1, C, B, A, che fa stampare C - B. A questo punto si ritorna al chiamante (sempre quello invocato con 2, A, B, C) che, non avendo più istruzioni da eseguire, termina e restituisce il controllo al suo chiamante (la prima invocazione della funzione). Ci troviamo sempre alla seconda istruzione nel ramo else, che stampa A - C, quindi si ha una nuova chiamata ricorsiva con i parametri 2, B, C, A, e così via.

 

[olegfresi]

Non capisco perchè la terza chiamata ricorsiva (terza istruzione dell'else) viene chiamata con (1,C,B,A) e non con (1,B,C,A). La chiamata precedente (ricorsione della seconda istruzione dell'else) è chiamata con (2,A,B,C) siccome l'ultima ricorsione è hanoi(n-1,b,c,a) mi aspettavo proprio questo, perchè sbaglio? Poi hai detto che una volta stampato C-B il controllo torna al chiamante (2,A,B,C) ma questo come fa a sapere che non ci sono altre istruzioni da eseguire?

 

[fabio93]

Un attimo, i parametri delle chiamate in ordine sono: 3,A,C,B; 2,A,B,C; 1,A,C,B -> ritorno al chiamante -> 1,C,B,A -> ritorno -> ritorno -> 2,B,C,A; 1,B,A,C -> ritorno -> 1,A,C,B -> ritorno -> ritorno(fine). Quindi la terza chiamata ricorsiva non è l'ultima istruzione dell'else, ma la prima.

 

[olegfresi]

Scusa, mi sono espresso male. Quello che non avevo capito è perchè la funzione ricorsiva della terza istruzione dell'else venisse chiamata con (1,B,C,A) anizichè con (1,C,B,A).Provo a riscrivere tutti i passaggi per vedere se ho capito.
1) Prima chiamata H1 con (3,A,C,B), il test dell'if fallisce e si entra nell'else
2) Seconda chiamata H2 con (2,A,B,C), il test dell'if fallisce e si rientra nell'else
3) Terza chiamata ricorsiva H3 con (1,A,C,B), il test dell'if passa con successo e stampa A-C.
4) Il controllo torna ad H2 con (2,A,B,C) che prosegue nell'else stampando A-B (perchè continua nell'else e non restituisce il controllo ad H1?)
5) Si passa alla terza istruzione dell'else ovvero la chiamata H4 con (1,B,C,A), il test dell'if passa con successo e viene stampato C-B
6) La chiamata torna ad H2 con (2,A,B,C) ma siccome sono finite le istruzioni dell'else restituisce il controllo ad H1 che non ho capito come ma sa che non ha più dischi sopra di se, quindi passa con successo l'if e stampa A-C.
Ma poi non ho capito come continua, come fa a passare il controllo di nuovo ad H2, se le chiamate ricorsive sono già finite andando a ritroso?

 

[fabio93]

Il mio post di ieri conteneva un errore, l'ho corretto e ho aggiunto le chiamate mancanti.
Le chiamate sono queste (ho indicato il numero della chiamata, i parametri attuali di ciascuna e cosa viene stampato da ciascuna):

                                 1
                              3,A,C,B
                               [A-C]
                            /          \      
                         /               \
                       /                   \
                     /                       \
                    2                          5
                 2,A,B,C                    2,B,C,A
                  [A-B]                      [B-C]
              /          \               /          \
             /            \             /            \
            3              4           6              7
         1,A,C,B        1,C,B,A     1,B,A,C        1,A,C,B
          [A-C]          [C-B]       [B-A]          [A-C]

L'ordine delle chiamate è: 1, 2, 3, ritorno, 4, ritorno, ritorno, 5, 6, ritorno, 7, ritorno, ritorno (fine).
Se sai cos'è un albero binario (struttura dati come quella disegnata) puoi immaginare l'ordine delle stampe a video come una in-visita di un albero binario. Vale a dire che, per ogni nodo, prima si visita il figlio sinistro, poi il nodo, infine il figlio destro. Ad ogni visita corrisponde una stampa. Perciò le stampe sono fatte come se i nodi dell'albero visitati fossero in ordine: 3,2,4,1,6,5,7

 

[olegfresi]

Perfetto, grazie mille Fabio, ora ho capito come funziona esattamente!

Post unito automaticamente: 7 Luglio 2019

Ma per curiosità, esiste una formalizzazione matematica di questo algoritmo? Cioè dimostrare che il numero minimo di mosse è 2^n-1 e che l'ordine del codice sia quello, in modo da poterlo generalizzare a k pioli?