Aλγόριθμος για τους πύργους του Hanoi

[shodanjr_gr]

Ρε παίδες, θέλω να βρω τρόπο να λύσω το πρόβλημα των πύργων του Hanoi για n δίσκους και 3 πύργους, ΧΩΡΙΣ να χρησιμοποιήσω αναδρομή σε αυτόν...

 

 

Έχω φάει όλη μου την μέρα σήμερα να βγάλω άκρη με αυτό το πρόβλημα, αλλά δεν μπορώ να βγάλω άκρη...ακόμα και η έρευνα μου στον γούγλη όσοι αλγόριθμοι βρήκα είτε χρησιμοποιούν αναδρομή είτε δεν μπορώ να τους καταλάβω (δεν έχω μάθει java...ακόμα :Ρ).

 

 

Οποιαδήποτε βοήθεια είναι ευπρόσκδεκτη :)

[teras]

Πύργοι του Ανόι χωρίς αναδρομή; Ιιιιιχ... ανατριχίλα :)

 

Είχα δει πριν 2-3 χρόνια μια μη αναδρομική λύση... και την καταχώνιασα στο υποσυνείδητό μου ως τραυματική εμπειρία. Mindbender με τα όλα του...

[shodanjr_gr]

Πέστο στον καθηγητή μας στην σχολή αυτό...

 

Το χειρότερο είναι ότι ξέρω (έτσι νομίζω τουλάχιστον) τον τρόπο με τον οποίο λύνεται, αλλά δεν μπορώ να τον διατυπώσω (μπλέκω τα μπούτια μου :Ρ)...

 

Someone help ρε παίδες...

[xpan]

πρέπει να έχω την λύση σε C ή Pascal κάπου καταχωνιασμένη. Δώσε μου λίγες ώρες και θα σου πω...

[xpan]

φίλε μου είσαι άτυχος. Έχω αφήσει όλες μου τις σημειώσεις στην Αθήνα την οποία θα επισκεφθώ σε 2 βδομάδες... Παρόλα αυτά έκανα ενα googling και βρήκα μια λύση σε Pascal... βέβαια είναι απο μη-αγγλικο site και ίσως να μη καταλάβεις τα ονόματα των μεταβλητών...

 

αν σε ενδιαφέρει ακόμα σου την στέλνω...

[shodanjr_gr]

Θα δείξει, στείλτε το λινκ για να δούμε :)

[xpan]

στέλνω pm

[rohamis]

Υπάρχει επαναληπτικός αλγόριθμος. Με 2 απλά βήματα :

 

1. μετακίνησε κατά την θετική φορα (ορίζεις μία, όποια θες) τον μικρότερο δίσκο.

2. Κάνε την μοναδική επιτρεπτή κίνηση που δεν αφορά τον μικρότερο δίσκο.

 

Παραθέτω εικόνα για να καταλάβεις την θετική φορά. Α μιλάμε πάντα για 3 πύργους...

[OratIos]

Αρχικό Μήνυμα από το μέλος rohamis (26 Οκτ. 2004 , 10:46)

 

Υπάρχει επαναληπτικός αλγόριθμος. Με 2 απλά βήματα :

 

1. μετακίνησε κατά την θετική φορα (ορίζεις μία, όποια θες) τον μικρότερο δίσκο.

2. Κάνε την μοναδική επιτρεπτή κίνηση που δεν αφορά τον μικρότερο δίσκο.

 

Παραθέτω εικόνα για να καταλάβεις την θετική φορά. Α μιλάμε πάντα για 3 πύργους...

 

 

Exeis Apolyto diko!!!!!

 

Endeiktika soy deino k ena link na to tsekareis kai monos soy!!! Hanoi Tower

 

Pantos an moy peis mexri to vrady tha soy exo ftia3ei ton kodika................... Apla steile na pm!!

[shodanjr_gr]

Αν μπορείς να το κάνεις θα σου ήμουν ευγνώμων. Το πρόβλημα είναι ότι το χρειάζομαι για Ν πύργους (τυχαίο αριθμό) και όχι για συγκεκριμένο νούμερο...

 

Πάντως μία τέτοια λογική είχα σκεφτεί και εγώ, απλά δεν μπόρεσα να την υλοποιήσω...

[OratIos]

#include <stdio.h>

#include "simpio.h"

#include "genlib.h"

 

 

main()

{

int i,j,n,thesia,thesib,thesic;

int a[100],b[100],c[100];

 

for (j=1 ; j<=100 ; j++) {

a[j]:=0;

b[j]:=0;

c[j]:=0;

}

 

 

printf("Dose arithmo N ton Kylindron toy pyrgoy!");

n=GetInteger();

 

for (i=1 ; i<=n-1 ; i++) { /*Gemizei ton pinaka a me atirthmoys apo to N mexri to 1,Exontas Pano pano to 1 poy einai mikrotero opos se ena sxhma pyrgon toy ANOI*/

a[0]=n;

a=a[i-1]-1;

}

thesia:=n;

thesib:=0;

thesic:=0;

while (c[n-1] <> 1) {

 

 

 

if(a[thesia-1]=1) then

b[thesib]:=1;

thesib:=++;

thesia--;

if (c[thesic]>a[thesia]) then

c[thesic+1]:=a[thesia];

thesic:=thesic+1;

thesia:=thesia-1;

else if (c[thesic]<a[thesia]) then

c[thesic]:=a[thesia+1];

thesic:=thesic-1;

thesia:=thesia+1;

 

 

if(b[thesib-1]=1) then

c[thesic]:=1;

thesic:=++;

thesib--;

if (a[thesia-1]>b[thesib-1]) then

a[thesia]:=b[thesib-1];

thesia:=thesia+1;

thesib:=thesib-1;

else if (a[thesia-1]<b[thesib-1]) then

b[thesib]:=a[thesia-1];

thesib:=thesib+1;

thesia:=thesia-1;

 

 

if(c[thesic-1]=1) then

a[thesia]:=1;

thesia:=++;

thesic--;

if (b[thesib-1]>c[thesic-1]) then

b[thesib]:=c[thesic-1];

thesib:=thesib+1;

thesic:=thesic-1;

else if (b[thesib-1]<c[thesic-1]) then

c[thesic]:=b[thesib-1];

thesic:=thesic+1;

thesib:=thesib-1;

 

}

 

 

 

 

 

 

 

 

 

 

 

 

}

[OratIos]

Vasika ayto einai mia geysh!!!Exo kapoio provlima me ton compiler ths C++ kai moy ta zalizei ........Sthn oysia kati psilolathakia xtypaei ,ta opoia tha ta ftia3o se ligo!Kai meta einai thema ektyposhs!!!

 

ayta.......Tha 3anapostaro enan pio olokliromeno code se ligaki!!

[OratIos]

#include <stdio.h>

#include "simpio.h"

#include "genlib.h"

 

 

main()

{

int i,j,n,thesia,thesib,thesic;

int a[100],b[100],c[100];

 

for (j=1 ; j<=100 ; j++) {

a[j]=0;

b[j]=0;

c[j]=0;

}

 

 

printf("Dose arithmo N ton Kylindron toy pyrgoy!");

n=GetInteger();

 

for (i=1 ; i<=n-1 ; i++) { /*Gemizei ton pinaka a me atirthmoys apo to N mexri to 1,Exontas Pano pano to 1 poy einai mikrotero opos se ena sxhma pyrgon toy ANOI*/

a[0]=n;

a=a[i-1]-1;

}

thesia=n;

thesib=0;

thesic=0;

while (c[n-1] != 1) {

 

 

 

if(a[thesia-1]=1) {

b[thesib]=1;

thesib++;

thesia--;

if (c[thesic]>a[thesia])

c[thesic+1]=a[thesia];

thesic=thesic+1;

thesia=thesia-1;

if(c[thesic]<a[thesia])

c[thesic]=a[thesia+1];

thesic=thesic-1;

thesia=thesia+1;

 

}

if(b[thesib-1]=1) {

c[thesic]=1;

thesic++;

thesib--;

if (a[thesia-1]>b[thesib-1])

a[thesia]=b[thesib-1];

thesia=thesia+1;

thesib=thesib-1;

if(a[thesia-1]<b[thesib-1])

b[thesib]=a[thesia-1];

thesib=thesib+1;

thesia=thesia-1;

 

}

if(c[thesic-1]=1) {

a[thesia]=1;

thesia++;

thesic--;

if (b[thesib-1]>c[thesic-1])

b[thesib]=c[thesic-1];

thesib=thesib+1;

thesic=thesic-1;

if(b[thesib-1]<c[thesic-1])

c[thesic]=b[thesib-1];

thesic=thesic+1;

thesib=thesib-1;

}

 

 

} /*While*/

 

 

 

 

 

 

 

} /*Main*/

[OratIos]

Ston parapano kodika den moy xtypaei tpt ston compiler,ara menei mono ena kalo print na ginei.............

[shodanjr_gr]

Για πες μου, τα thesia++ και thesia-- τι σημαίνουν; Το μεγαλύτερο κομμάτι το καταλαβαίνω. Εκεί ψιλοκολλάω (δεν έχω κάνει πολύ c).

[OratIos]

to thesia ++ ay3anei thn timh toy thesia kata 1 monada kai antistoixa to allo thn meionei!

 

Sthn oysia exo kanei 3 pinakes sthlhkai paizo me to pano pano stoixeio toys!

[OratIos]

to etrexes esy??Soy vgazei kanena provlima??Ego pantos dne mporo giati kapoio provlima paizei k den mporei na vrei ta executes.........

[shodanjr_gr]

Δεν πρόκειται να το τρέξω. Αύριο απλά θα το μετατρέψω σε αλγόριθμο (αυτή την παπαρία που κάναμε στο Λύκειο) για να το δώσω στον καθηγητή.