OliForum Matematico

Ciao a tutti.... dovrei fare un algoritmo che mi trovi la soluzione del gioco della torre di Hanoi... l'unica cosa a cui sono riuscito ad arrivare è:

- Le mosse minime per risolvere il gioco sono $ 2^n-1 $;

- Nel caso in cui il numero dei dischi è dispari il PRIMO piattelo va spostato nel terzo bastoncino... se è il numero di dischi è pari va spostato nel secondo bastoncino....

- (Non so se è importante) Penso basti scoprire la prima metà delle mosse... la seconda metà dovrebbe essere la stessa però invertita.. faccio un esempio nel caso in cui si hanno 3 dischi:
(I numeri rappresentano il numero dei dischi in ogni bastoncino):

0) 3 0 0 (stato inziziale)
1) 2 0 1
2) 1 1 1
3) 1 2 0
4) 0 2 1
5) 1 1 1
6) 1 0 2
7) 0 0 3

Come si può notare dalla 4 alla 7 sono uguali come la serie dalla 0 alla 3... non so se puo servire....

Ora... c'è una regola generale che posso usare per continuare il gioco?
Per l'implemntazione del codice non c'è problema... la mia difficoltà sta "solo" nel capire che regola utilizzare per decidere quale piattello spostare e dove...

Grazie di cuore...

(Per sicurezza riporto cosa bisogna fare nella torre di Hanoi.... per chi lo sapesse non ha bisogno di continuare a leggere in breve nel gioco della Torre di Hanoi vi sono tre bastoncini sui quali si possono impilare n piattelli a forma di anello con raggio crescente. La regola prevede che si possa spostare un piattello alla volta e che non si possano sovrapporre piattelli di raggio maggiore a quelli già impilati su di un bastoncino. L’obiettivo è quello di spostare tutti i piattelli da un bastonicino iniziale, sul quale sono impilati correttamente dal più grande al più piccolo gli n piattelli, ad uno degli altri due. )

la torre di hanoi e' un classico gioco di logica a dimostrazione per induzione:
si puo' mostrare che la soluzione per $ ~n+1 $ dischi equivale a
1) svolgere quella per $ ~n $ dischi spostando la pila nel palo centrale,
2) spostare l'$ ~n+1 $-esimo disco nel palo laterale
3) risvolgere la soluzione per $ ~n $ dischi spostando la pila nel palo laterale
quindi $ ~S_{n+1}=2S_n+1 $

La torre di hanoi prevede di spostare la pila da un palo laterale all'altro, quindi nominati i tre pali 1,2,3 con 1 e 3 i pali laterali e 1 quello di partenza, trovata una volta la soluzione per $ ~n $ dischi, la soluzione per $ ~n+1 $ si ha prendendo quella per $ ~n $ ed effettuando lo scambio $ ~2\leftrightarrow 3 $, aggiungere la mossa che porta l'$ ~n+1 $-esimo disco su 3 e poi riprendendo quella per $ ~n $ ed effettuando lo scambio $ ~1\leftrightarrow 2 $

SkZ ha scritto:... e poi riprendendo quella per $ ~n $ ed effettuando lo scambio $ ~1\leftrightarrow 2 $

Non ho capito bene quest'ultimo pezzo... grazie

L'algoritmo è sorprendentemente semplice: fai una procedura ricorsiva che sposta una torre da una posizione all'altra.

Ad esempio: Come risultato ottieni una successione di SpostaDisco(a, b), che è la soluzione.
Per esempio, puoi dirgli:

Il problema è questo... non penso posso farla ricorsiva... esattamente nell'esercizio viene richiesto di 3 stack che rappresentano i 3 bastoncini della torre di hanoi... quindi generare la soluzione spostando gli elementi da uno stack all'altro...

per quanto riguarda il linguaggio.. costruzione degli stack, push, pop e cose varie non nessun problema... il problema è nel costruire l'algoritmo che mi generi la soluzione in quanto non riesco a trovare una soluzione generale del problema...
Forse la posso ricavare da quello che diceva Skz ponendo n=1 e da li ricavare tutte le altre soluzioni...

$ ~1\leftrightarrow 2 $ ovvero l'1 diventa 2 e il 2 diventa 1: ove ti compare il 2 lo cambi con l'1, ove compare l'1 metti il 2

Sono riuscito a torvare l'algoritmo solo per $ n=1 $ e $ n=2 $:

MindFlyer ha scritto:L'algoritmo è sorprendentemente semplice: fai una procedura ricorsiva che sposta una torre da una posizione all'altra.

Ad esempio:

Codice: Seleziona tutto

// sposta una torre alta "altezza" dalla posizione "start" alla posizione "end", usando "aux" come posizione ausiliaria

SpostaTorre(altezza, start, end, aux)
   se (altezza>0) allora
      SpostaTorre(altezza-1, start, aux, end)
      SpostaDisco(start, end)
      SpostaTorre(altezza-1, aux, end, start)

Come risultato ottieni una successione di SpostaDisco(a, b), che è la soluzione.
Per esempio, puoi dirgli:

Codice: Seleziona tutto

SpostaDisco(start, end)
   scrivi("Sposta un disco da ", start, " a ", end)

Oppure forse posso utilizzare questa soluzione anche se ho questi stack.... o se non riesco forse posso trasformarla da ricorsiva a iterativa....

comunque.. grazie per l'aiuto

Cioé.


Voglio dire, la procedura SpostaDisco(a,b) è esattamente ciò che tu chiami a->b. Ovvero, poppa lo stack a e pusha sullo stack b.


O no????


Forse stai dicendo che devi usare un linguaggio così peculiare che non ti permette di fare ricorsioni (che linguaggio è?)?

No no... è C++.. forse semplicemente non capisco la ricorsione...

spiego come è strutturato il mio programma...
Ho creato una classe bastoncino e all'interno ci sono i metodi Push, Pop etc etc...

nel main ho creato gli oggetti A, B e C che rappresentano i tre bastoncini della torre.. Ora tornando alla ricorsione:


Ora mi sembra di aver capito che la funzione "SpostaDisco" faccia solo una stampa... quindi eliminando momentaneamente quella, la funzione ricorsiva diventa questa:
Ora qui stanno i dubbi... se ho capito bene la funzione 2 viene richiamata subito dopo la funzione 1... ma... la funzione 1 non richiama se stessa prima di passare alla 2?? (non so se mi sono espresso bene.. spero di si) e così per la prima, per la seconda, la terza... n-esima volta fino a quando n=0? e quando si arriva alla funzione 2?

il secondo dubbio è: come faccio a richiamare il metodo push e il metodo pop? qui mi sembra che sposto solo la posizione dei bastoncini ma non il loro contenuto...

sicuramente c'è qualcosa che mi sfugge m anon capisco dove e cosa....

grazie per l'aiuto

Boia.

A parte che hai scazzato l'ordine di A, B, C nel ricopiare il mio algoritmo... Stai attento e correggi o chiaramente non funzionerà...

Veniamo al dunque. Ti dicevo che la procedura SpostaDisco(A,B) può fare quello che cappero ti pare. Ad esempio: non vuoi che scriva nulla, ma vuoi che poppi e pushi 2 pile? Eccotela: Al posto di PopStack e PushStack, mettici i tuoi metodi per poppare e pushare. Ah, naturalmente devi rimettere SpostaDisco nell'algoritmo nel punto in cui l'hai tolta, altrimenti è palese che quella roba non calcolerà una fava!
Se anche così non è chiaro, mi arrendo.

No no... sei stato chiarissimo... non avevo ben compreso cosa faceva la funzione sposta disco...

ti ringraziio tantissimo e scusa se ho protato la tua pazienza al limite

Nessun problema, l'importante è che ci siamo capiti. Buona programmazione!

grazie ancora

niente.. penso di aver impostato male il programma... non mi riesce