Discussione:Torre di Hanoi

Algoritmo ricorsivo

L'algoritmo ricorsivo sarebbe perfetto se non fosse che non rispetta la regola base del gioco sopra descritta che dice che i dischi si possono mettere un disco solo su un altro disco più grande, mai su uno più piccolo... quindi o la regola è sbagliata (e non mi sembra) o la regola è facoltativa (può darsi pure ma allora il gioco è molto ma molto più banale) o l'algoritmo ricorsivo è sbagliato. Ai posteri, o ai meglio informati sull'argomento, l'ardua sentenza... --Accurimbono 10:05, 5 apr 2007 (CEST)

O forse l'algoritmo è spiegato male, la fase 1 Sposta i primi n-1 dischi da A a C. Questo lascia il disco n da solo sul paletto A, dovrebbe essere spiegata meglio, così sembra che lo spostamento da A a C degli n-1 dischi sia banalmente sequenziale. Ciao, --Accurimbono 10:08, 5 apr 2007 (CEST)

Forse non è spiegato molto bene, ma è una cosa tipica della matematica quella di ricondursi ad un caso più piccolo. L'idea è: se so risolvere il problema di spostare n-1 dischi da una colonna ad un altra, come risolvo il problema di spostarne n? In questo modo di ragionare, il problema su n-1 dischi si considera già risolto (è sostanzialmente il principio alla base dell'induzione matematica. Ciao, Salvatore Ingala (conversami) 18:05, 5 apr 2007 (CEST)

OK, l'induzione matematica l'ho digerita tempo fa quando ho dato il beneamato corso di analisi 1, e a seguire informatica. :) La mia obiezione non riguardava la parte induttiva dell'algoritmo ma la fase 1: la difficoltà della Torre di Hanoi sta proprio nello spostare i dischi senza mettere dischi grandi sopra dischi più piccoli, l'algoritmo illustrato teoricamente funziona ma in pratica (per gli umani che vogliano ricordare tutti i passi a memoria) non è di grande aiuto. Spostare il disco da A a B per n=1 è banale, quello che non è banale (e andrebbe sottolineato) è "spostare i primi n-1 dischi da A a C" quando n-1 è un numero elevato. Andrebbe spiegato meglio anche che nello "spostare i primi n-1 dischi da A a C" si deve rispettare la regola: "mettere un disco solo su un altro disco più grande, mai su uno più piccolo". Spero di essermi spiegato meglio. Ciao, --Accurimbono 20:12, 5 apr 2007 (CEST)

Se il problema è solo di carattere espositivo, ti invito a modificare la voce riformulando le frasi come ritieni opportuno. Ma l'algoritmo in sé non può essere semplificato più di così, perché l'uso della ricorsione è essenziale e richiede quel tipo di scomposizione del problema di cui ti parlavo prima (risolvo il caso n dopo aver risolto il caso n-1). Per il problema con 4 dischi, la lista delle 15 (2⁴ - 1) mosse per spostare tutti i dischi dalla colonna A alla colonna C è la seguente (ho numerato i dischi dal più piccolo al più grande, e, ad esempio, con 2 A C indico lo spostamento del secondo disco dalla colonna A alla colonna C):

1 A B \
2 A C  \
1 B C   \
3 A B    + Sposta 4-1 = 3 dischi dalla colonna A alla colonna B
1 C A   /
2 C B  /
1 A B /

4 A C sposta il disco 4 dalla colonna A alla colonna C

1 B C \
2 B A  \
1 C A   \
3 B C    + Sposta 4-1 = 3 dischi dalla colonna B alla colonna C
1 A B   /
2 A C  /
1 B C /

Ad alto livello, l'algoritmo consiste di questi tre passi. Ora, la sequenza delle istruzioni del primo blocco di 7 mosse dell'ultimo blocco di 7 mosse è risolta con lo stesso algoritmo; ad esempio, per le prime 7 mosse:

1 A B \
2 A C  + Sposta 2 dischi dalla colonna A alla colonna C
1 B C /

3 A B Sposta il disco 3 dalla colonna A alla colonna B

1 C A \
2 C B  + Sposta 2 dischi dalla colonna C alla colonna B
1 A B /

L'algoritmo è lo stesso, ma su un'istanza più piccola del problema. Di nuovo si può procedere ricorsivamente sui blocchi di 3 istruzioni.

Com'è usanza comune (e probabilmente necessaria) nella descrizione di un algoritmo ricorsivo, la spiegazione si limita solo al primo livello, dato che poi l'algoritmo si ripete identico ai livelli inferiori.

Probabilmente sarebbe il caso di mostrare un'implementazione informatica dell'algoritmo per renderne più evidente il funzionamento. Ciao, Salvatore Ingala (conversami) 02:50, 6 apr 2007 (CEST)

Ho dovuto togliere quello che avevo scritto sulla complessità computazionale.Non riesco a scrivere 2^(n-1), come si fa?

Collegamenti esterni modificati

Gentili utenti,

ho appena modificato 1 collegamento esterno sulla pagina Torre di Hanoi. Per cortesia controllate la mia modifica. Se avete qualche domanda o se fosse necessario far sì che il bot ignori i link o l'intera pagina, date un'occhiata a queste FAQ. Ho effettuato le seguenti modifiche:

• Aggiunta del link all'archivio https://web.archive.org/web/20040211132211/http://www.kernelthread.com/hanoi/ per http://www.kernelthread.com/hanoi/

Fate riferimento alle FAQ per informazioni su come correggere gli errori del bot.

Saluti.—InternetArchiveBot (Segnala un errore) 05:15, 11 mag 2019 (CEST)