Ho già proposto questo gioco in un altro forum, ma forse qui ha più visibilità (in un forum che si intitola puffi non si vanno a cercare esercizi, di solito)
<BR>
<BR>La torre di Hanoi è composta da tre pioli verticali. In uno di questi sono infilati dei dischi in ordine di grandezza (il più piccolo è quello più in alto). Lo scopo è ricomporre la pila di dischi in uno dei pioli liberi spostando un solo disco per volta e senza mai mettere un disco più grande su uno più piccolo. Quante mosse servono per ricomporre una pila di n dischi?
<BR>
<BR>Ciao
<BR>
la torre di Hanoi
Moderatore: tutor
l\'avevo risolto un mesetto fa e avevo anche mandato il gioco a diverse persone per far capire meglio il funzionamento, come problema è simpatico
<BR>
<BR>leggenda orientale:
<BR>c\'è un santuario dove dei monaci si occupano di una torre di hanoi costruita con 64 dischi di bronzo, messa lì da dio il giorno della creazione, ogni giorno spostano uno di questi dischi seguendo le regole già dette, quando avranno finito di spostare da un piolo all\'altro la torre il mondo finirà.
<BR>Quando sarebbe dovuto finire-finirà il mondo?
<BR>
<BR>(ma calcolatevi la formula generale che fate prima)
<BR>
<BR>leggenda orientale:
<BR>c\'è un santuario dove dei monaci si occupano di una torre di hanoi costruita con 64 dischi di bronzo, messa lì da dio il giorno della creazione, ogni giorno spostano uno di questi dischi seguendo le regole già dette, quando avranno finito di spostare da un piolo all\'altro la torre il mondo finirà.
<BR>Quando sarebbe dovuto finire-finirà il mondo?
<BR>
<BR>(ma calcolatevi la formula generale che fate prima)
_k_
Diciamo che i sacerdoti siano dei superman e spostino 1 disco al secondo lavorando giorno e notte... Ci impiegherebbero soltanto 600 miliardi di anni a finire....
<BR>Comunque la versione completa della storiella è che c\'è una torre di Hanoi nella città di benares, in India, composta da 64 dischi d\'oro. Prima che i sacerdoti avranno finito l\'opera \"il tempio cadrà in polvere e il mondo scomparirà in un boato di tuono\".
<BR>Comunque la versione completa della storiella è che c\'è una torre di Hanoi nella città di benares, in India, composta da 64 dischi d\'oro. Prima che i sacerdoti avranno finito l\'opera \"il tempio cadrà in polvere e il mondo scomparirà in un boato di tuono\".
Dunque,
<BR>
<BR>Per fare una fila di n dischi occorre prima spostare n-1 dischi su di un piolo solo e quindi spostare l\'ennesimo disco sul piolo rimasto libero e ripetere le operazioni che abbiamo già fatto per costruire la piramide di n-1 dischi, solo che stavolta sul disco ennesimo.
<BR>
<BR>Notare che: quello che ho detto si può sempre fare perchè una volta costruita la piramide di n-1 dischi si ha un piolo vuoto e un altro con l\'ennesimo disco e quindi non si verificherà (a meno di stupidi tentativi) di metter un disco maggiore sopra un minore.
<BR>
<BR>Morale della favola gli spostamenti per fare una piramide di n dischi sono 2 volte le operazioni che servono per fare una piramide di n-1 dischi aumentate di 1.
<BR>
<BR>Calcoliamoci allora gli spostamenti per fare una piramide di un disco, una di due e generalizziamo il tutto usando l\'induzione.
<BR>
<BR>Allora: piramide di un piolo 1 spostamento, piramide di due pioli tre spostamenti.
<BR>
<BR>Errore basta la piramide di due pioli...(cioè ne basta una qualsiasi, viene anche con un disco solo...però non ho voglia di cambiare quello che ho già scritto...)
<BR>
<BR>Comunque scriviamo 3 come (2^2)-1, moltiplichiamo per 2 e aggiungiamo 1
<BR>Diventa (2^3) -1. Trovato il nostro punto di partenza vero vediamo usiamo l\'induzione: moltiplichiamo (2^(n-1)-1) per 2 e aggiungiamo 1. Con facili calcoli vediamo che viene 2^(n)-1 che è quindi il numero di operazioni necessarie per spostare una fila di n pioli...
<BR>
<BR>QED? <IMG SRC="images/forum/icons/icon21.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: colin il 07-12-2002 15:22 ]
<BR>
<BR>Per fare una fila di n dischi occorre prima spostare n-1 dischi su di un piolo solo e quindi spostare l\'ennesimo disco sul piolo rimasto libero e ripetere le operazioni che abbiamo già fatto per costruire la piramide di n-1 dischi, solo che stavolta sul disco ennesimo.
<BR>
<BR>Notare che: quello che ho detto si può sempre fare perchè una volta costruita la piramide di n-1 dischi si ha un piolo vuoto e un altro con l\'ennesimo disco e quindi non si verificherà (a meno di stupidi tentativi) di metter un disco maggiore sopra un minore.
<BR>
<BR>Morale della favola gli spostamenti per fare una piramide di n dischi sono 2 volte le operazioni che servono per fare una piramide di n-1 dischi aumentate di 1.
<BR>
<BR>Calcoliamoci allora gli spostamenti per fare una piramide di un disco, una di due e generalizziamo il tutto usando l\'induzione.
<BR>
<BR>Allora: piramide di un piolo 1 spostamento, piramide di due pioli tre spostamenti.
<BR>
<BR>Errore basta la piramide di due pioli...(cioè ne basta una qualsiasi, viene anche con un disco solo...però non ho voglia di cambiare quello che ho già scritto...)
<BR>
<BR>Comunque scriviamo 3 come (2^2)-1, moltiplichiamo per 2 e aggiungiamo 1
<BR>Diventa (2^3) -1. Trovato il nostro punto di partenza vero vediamo usiamo l\'induzione: moltiplichiamo (2^(n-1)-1) per 2 e aggiungiamo 1. Con facili calcoli vediamo che viene 2^(n)-1 che è quindi il numero di operazioni necessarie per spostare una fila di n pioli...
<BR>
<BR>QED? <IMG SRC="images/forum/icons/icon21.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: colin il 07-12-2002 15:22 ]
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Comunque scriviamo 3 come (2^2)-1, moltiplichiamo per 2 e aggiungiamo 1
<BR>Diventa (2^3) -1. Trovato il nostro punto di partenza vero vediamo usiamo l\'induzione: moltiplichiamo (2^(n-1)-1) per 2 e aggiungiamo 1. Con facili calcoli vediamo che viene 2^(n)-1 che è quindi il numero di operazioni necessarie per spostare una fila di n pioli...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Per applicare correttamente l\'induzione non devi dimostrare che P(0) ---> P(1) e P(n) ---> P(n+1) (la prima parte sarebbe già compresa nella seconda!) ma che P(0) è vera, e poi che P(n)---> P(n+1).
<BR>Cioè non devi dimosrare che SE la tua formula è valida per due pioli ALLORA è valida per tre, ma che E\' effettivamente valida per due pioli. Come hai notato tu stesso, in realtà si può anche partire dalla torre di un piolo, per la quale è ovvio che è richiesto uno spostamento. Il passo induttivo poi è corretto.
<BR>Comunque scriviamo 3 come (2^2)-1, moltiplichiamo per 2 e aggiungiamo 1
<BR>Diventa (2^3) -1. Trovato il nostro punto di partenza vero vediamo usiamo l\'induzione: moltiplichiamo (2^(n-1)-1) per 2 e aggiungiamo 1. Con facili calcoli vediamo che viene 2^(n)-1 che è quindi il numero di operazioni necessarie per spostare una fila di n pioli...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Per applicare correttamente l\'induzione non devi dimostrare che P(0) ---> P(1) e P(n) ---> P(n+1) (la prima parte sarebbe già compresa nella seconda!) ma che P(0) è vera, e poi che P(n)---> P(n+1).
<BR>Cioè non devi dimosrare che SE la tua formula è valida per due pioli ALLORA è valida per tre, ma che E\' effettivamente valida per due pioli. Come hai notato tu stesso, in realtà si può anche partire dalla torre di un piolo, per la quale è ovvio che è richiesto uno spostamento. Il passo induttivo poi è corretto.
[img:2sazto6b]http://digilander.iol.it/daniel349/boy_math_md_wht.gif[/img:2sazto6b]