Torre di Hanoi
-
MindFlyer
Penso di aver "scoperto" un altro modo... iterativo...
Se i dischi sono dispari:
- muovo il disco più piccolo in senso antiorario (1->3 , 3->2 , 2->1)
- muovo un altro disco nel piolo dove non c'è il disco 1
finchè nel piolo 3 non ci sono tutti i dischi.
Se i dischi sono pari:
il disco più piccolo si deve muovere in senso orario...
Se i dischi sono dispari:
- muovo il disco più piccolo in senso antiorario (1->3 , 3->2 , 2->1)
- muovo un altro disco nel piolo dove non c'è il disco 1
finchè nel piolo 3 non ci sono tutti i dischi.
Se i dischi sono pari:
il disco più piccolo si deve muovere in senso orario...
-
MindFlyer
inviato...
però penso che si possa creare una struttura ricorsiva... un pò diversa...
Questo pezzo di codice lo dovrei ripetere 3 volte... però sostituendo la seconda volta
A con C;
C con B;
B con A;
e la terza volta
A con B;
C con A;
B con C;
O meglio ancora.. dovrei solo sostiuire
A con C;
C con B;
B con A;
ogni volta che chiami la funzione...
però penso che si possa creare una struttura ricorsiva... un pò diversa...
Codice: Seleziona tutto
C.Push(A.Pop());
C.Chiudi();
if((B.ContaEle()==0) || A.Ultimo()<B.Ultimo()){
B.Push(A.Pop());
B.Chiudi();
}
else{
A.Push(B.Pop());
A.Chiudi();
}
A.Visualizza();
B.Visualizza();
C.Visualizza();
A con C;
C con B;
B con A;
e la terza volta
A con B;
C con A;
B con C;
O meglio ancora.. dovrei solo sostiuire
A con C;
C con B;
B con A;
ogni volta che chiami la funzione...
-
MindFlyer
Codice: Seleziona tutto
int Antiorario(Peg A,Peg B,Peg C){
C.Push(A.Pop());
if(C.ContaEle()==dischi)
return 0;
if(A.ContaEle()==0)
A.Push(B.Pop());
else if(B.ContaEle()==0)
B.Push(A.Pop());
else if(A.Ultimo()<B.Ultimo())
B.Push(A.Pop());
else
A.Push(B.Pop());
Antiorario(C,A,B);
}
)... solo un problema... funziona per n=1,3 e 5.... con $ n \ge 7 $ mi trova la soluzione esatta... però non esce dalla funzione provacando così un errore in run-time...
Devo postare tutto il codice?
-
MindFlyer
Allora. Ho guardato la cosa che mi hai mandato in mp.
Ho reimplementato lo stack in un modo più semplice (non ha senso implementarlo "al contrario" solo per poterlo stampare comodamente nel verso giusto!). Ho corretto svariati errori coi puntatori che lo facevano crashare.
Ho aggiunto la procedura ricorsiva SpostaTorre, che ti dicevo all'inizio.
Prova ad eseguirlo e vedrai che funziona, con l'accorgimento che la visualizzazione delle pile viene fatta dall'alto al basso, e non come prima dal basso all'alto. Se non ti piace, modifica il metodo Bastoncino.Visualizza() come ti pare.
Se hai problemi a capire come funziona, chiedi pure (qui, non in messaggi privati).
Ho reimplementato lo stack in un modo più semplice (non ha senso implementarlo "al contrario" solo per poterlo stampare comodamente nel verso giusto!). Ho corretto svariati errori coi puntatori che lo facevano crashare.
Ho aggiunto la procedura ricorsiva SpostaTorre, che ti dicevo all'inizio.
Prova ad eseguirlo e vedrai che funziona, con l'accorgimento che la visualizzazione delle pile viene fatta dall'alto al basso, e non come prima dal basso all'alto. Se non ti piace, modifica il metodo Bastoncino.Visualizza() come ti pare.
Se hai problemi a capire come funziona, chiedi pure (qui, non in messaggi privati).
Codice: Seleziona tutto
// File Hanoitwr.h
#include<iostream>
using namespace std;
class Bastoncino{
/* Attributi */
private:
typedef struct stack{
int raggio;
stack *succ;
};
stack *fst;
public:
/* Costruttore */
Bastoncino(){
fst=NULL;
}
/* Distruttore */
~Bastoncino(){
stack *tmp;
while(fst!=NULL){
tmp=fst->succ;
free(fst);
fst=tmp;
}
}
/* Inserisce un elemento nello stack */
void Push(int elemento){
stack *tmp=new stack;
tmp->raggio=elemento;
tmp->succ=fst;
fst=tmp;
}
/* Preleva il primo elemento dallo stack */
int Pop(){
if(fst==NULL) return -1;
int r=fst->raggio;
stack *tmp=fst;
fst=tmp->succ;
free(tmp);
return r;
}
void Inizializza(int elementi){
for(int i=elementi;i>0;i--) Push(i);
}
/* Stampa a video dello stack */
void Visualizza(){
stack *tmp=fst;
while(tmp!=NULL){
cout<<tmp->raggio<<" ";
tmp=tmp->succ;
}
}
};Codice: Seleziona tutto
// File Hanoi.cpp
#include "Hanoitwr.h"
#include <cmath>
void SpostaDisco(Bastoncino *start, Bastoncino *end){
end->Push(start->Pop());
}
void SpostaTorre(int altezza, Bastoncino *start, Bastoncino *end, Bastoncino *aux){
if(altezza==0) return;
SpostaTorre(altezza-1,start,aux,end);
SpostaDisco(start,end);
SpostaTorre(altezza-1,aux,end,start);
}
void main(){
int dischi;
Bastoncino A,B,C;
cout<<"Inserire il numero dei dischi: ";
cin>>dischi;
cout<<endl<<"Numero minimo di mosse per risolvere il gioco della torre di Hanoi: "
<<pow(2,(double)dischi)-1<<" mosse"<<endl<<endl;
A.Inizializza(dischi);
cout<<"Bastoncino A: "; A.Visualizza(); cout<<endl;
cout<<"Bastoncino B: "; B.Visualizza(); cout<<endl;
cout<<"Bastoncino C: "; C.Visualizza(); cout<<endl;
cout<<endl<<"Sto spostando la torre da A a C..."<<endl;
SpostaTorre(dischi,&A,&C,&B); cout<<endl;
cout<<"Bastoncino A: "; A.Visualizza(); cout<<endl;
cout<<"Bastoncino B: "; B.Visualizza(); cout<<endl;
cout<<"Bastoncino C: "; C.Visualizza(); cout<<endl;
}si infatti poi li avevo cambiati alcuni metodi della classe... ma evidentemente ancora non era sufficente...
Ahhhhh forse ho capito quello che non mi è chiaro... in pratica hai la certezza dell'indirizzo solo dell'ultimo elemento...quello è fisso... non il primo elemento... il primo elemento varia in base agli spostamenti.... giusto?
Onestamente non avevo neanche preso in considerazione una soluzione del genere...
grazie infinite...
P.S.: Ehi fino a gennaio il copyright ce l'ho io di quell'esercizio guai a chi lo tocca
ma non i diritti d'autore 
Ahhhhh forse ho capito quello che non mi è chiaro... in pratica hai la certezza dell'indirizzo solo dell'ultimo elemento...quello è fisso... non il primo elemento... il primo elemento varia in base agli spostamenti.... giusto?
Onestamente non avevo neanche preso in considerazione una soluzione del genere...
grazie infinite...
P.S.: Ehi fino a gennaio il copyright ce l'ho io di quell'esercizio guai a chi lo tocca
ma non i diritti d'autore -
MindFlyer
Non ho capito cosa vuoi dire.Sosuke ha scritto:Ahhhhh forse ho capito quello che non mi è chiaro... in pratica hai la certezza dell'indirizzo solo dell'ultimo elemento...quello è fisso... non il primo elemento... il primo elemento varia in base agli spostamenti.... giusto?
Ho implementato uno stack con una lista nel modo più naturale, ovvero dove il primo elemento è quello nella testa dello stack. Poiché tutte le operazioni su stack vengono fatte sull'elemento di testa, questa è la soluzione più logica (nota che push e pop prendono tempo costante nella mia implementazione, mentre nella tua tempo lineare, che è un'esagerazione!!!).
Per fare le cose in modo più coerente, potresti aggiungere un test nel metodo Bastoncino.Push(), per verificare che il disco di testa non abbia raggio minore del disco che si vuole inserire.