Hanoi Turm Problem iterativ lösen
lima-city → Forum → Programmiersprachen → Python
argument
aufgabe
beenden
bewegen
code
dank
feld
folgenden code
frage
funktion
kleinste scheibe
programm
scheibe
spiel
start
text
turm
url
verstehen
versuchen
-
Hey Leutz,
ich hab da ein Problem das ich irgendwie nicht gebacken bekomme :/
Ich soll das Hanoi Spiel Problem mit Python iterativ lösen.
Hab auch C und Java varianten gefunden aber bekomme sie einfach nicht portiert -.-
Das Spiel besteht aus drei Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C zu versetzen. Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.
Hätte vielleicht irgendwer eine iterative Fassung? Oder könnte mir Hilfestellung mit Beispiel Code geben?!
Danke schonmal im voraus
LG DeX -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Deine Hausaufgaben machen ist doof
Ich hab die Türme nie gelöst, aber hier wäre nen Ansatz:
http://de.wikipedia.org/wiki/Türme_von_Hanoi#Iterativer_Algorithmus
Jenachdem wie gut du bist würde ich die Stäbe und die Schreiben als Objekte definieren, warum ist einfach der Anschaulichkeit halber, und dann ist es eine whileschleife, welche jeweils die Scheiben von der kleinsten an versucht nach rechts rüber zu legen. Wenn das mit der kleinsten nicht geht nimmt man die zweit kleinste, und dannach die drittkleinste.
Ich denke wenn du dir das Bild oben anschaust, dann wirst du schnell merken, dass die scheiben immer nur nach rechts, wenn möglich, gelegt werden.
Ich hoffe das hilft.
Liebe Grüße -
Jo is ne HA ... hab zu spät angefangen und muss noch andere lösen *g*
Den Wiki Ansatz hab ich natürlich als erstes gelsen, wobei der eher schwammig ist :/
Besser:
Start: if (n 'mod' 2) == 0 then bewegen Sie die kleinste Scheibe zur Hilfsstange else bewegen Sie die kleinste Scheibe zur Zielstange So lange nicht alle Scheiben am Ziel sind: 1. bewegen Sie die kleinste Scheibe zu der Stange, wo diese als letztes nicht gewesen ist. 2. machen Sie eine legale Bewegung, ohne die kleinste Scheibe zu bewegen (nur eine Bewegung ist immer möglich).
Jedoch bin ich in Python nich besonders ...wegen Objekten und co -.- -
Ui, ne, öhhh, ich geb mal nen groben Hinweis in Schritten:
S1, S2, S3 seien die Scheiben, die Türme seien T1, T2, T3
Alle Scheiben befinden sich der richtigen Größe nach auf T1
Du willst von T1 nach T3
S1 1 nach Links auf T3
eine von S1 unterschiedliche Scheibe bewegbar?
Ja, S2 um 2 nach Links auf T2
Beginne von forne!
S1 1 nach Links auf T2
eine von S1 unterschiedliche Scheibe bewegbar?
Ja, S3 um 1 nach Links
Beginne von forne!
S1 1 nach Links auf T1
eine von S1 unterschiedliche Scheibe bewegbar?
Ja, S2 um 2 nach Links nach T3
Beginne von forne!
........
Weiter habe ich keine Lust
Ich hoffe du siehst das Muster. In Pseudocode siehts so aus vermutlich:
while ( nicht alle verschoben ) {
verschiebe S1 um mindestens einen nach Links
if ( kann man was anderes als S1 nach Links verschieben? ) {
verschiebe des andere als S1 um mindestens einen nach Links
}
}
Nun bissel offensichtlicher?
Liebe Grüße -
Check noch nicht so ganz wie ich es speichern soll das alle, oder nur teile von einem Turm zum anderen verschoben wurden :/
-
lordcodex schrieb:
Ich geb dir mal eine Java-Klasse (Python kann ich leider nicht) für einen Turm, vllt hilfts dir zum Verstehen:
Check noch nicht so ganz wie ich es speichern soll das alle, oder nur teile von einem Turm zum anderen verschoben wurden :/class Tower { int tos; // Top Of Stack : Spitze des Stapels int t[]; // Der Stapel: t[0] == unten, t[tos] == oben public Tower (int nTowers) { tos = 0; t = new int [nTowers]; } public void push (int i) { t[tos++] = i; } public int pop () { return t[--tos]; } }
Beitrag zuletzt geändert: 21.5.2012 22:17:40 von hackyourlife -
Ich hab hier nen recht guten C Code, das Problem ist das meine Python Kenntnisse nicht ausreichen um das sauber zu portieren -.-
#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <time.h> void sleep( clock_t wait ); // Wieviele Scheiben? #define MAX_SCHEIBEN 10 int main(int argc, char *argv[]) { int i, j=0; int a, b, c, atop, btop, ctop; int hanoi[3][MAX_SCHEIBEN]= {0}; int usedScheiben = 8; int top[3]= {0}; int start=0; // erster, zu testender turm int steps=0; //zählt die benötigten Schritte char scheibe[MAX_SCHEIBEN+1][29]= {" ", " [_] ", " [___] ", " [_____] ", " [_______] ", " [_________] ", " [___________] ", " [_____________] ", " [_______________] ", " [_________________] ", " [___________________] " }; for (i=0; i<usedScheiben; i++) hanoi[0][i]=usedScheiben-i; top[0]= usedScheiben-1; //voller Turm top[1]= -1; //leer top[2]= -1; // Main Loop while( 1 ) { // Ausgabe for(i=usedScheiben-1; i>=0; i--) printf("%s%s%s\n", scheibe[hanoi[0][i]], scheibe[hanoi[1][i]], scheibe[hanoi[2][i]] ); printf("tops%10i%15i%15i\n", top[0], top[1], top[2]); printf("steps: %i start: %i", steps, start); printf("\n\n\n\n\n\n\n\n\n\n\n"); //pause 500ms sleep(500); // Berechnung for(i=0; i<3; i++) { //start=0; a = (start+i)%3; b = (start+i+1)%3; c = (start+i+2)%3; atop = top[a]; btop = top[b]; // einer der beiden anderen Türme ctop = top[c]; // einer der beiden anderen Türme //printf("top a:%i for: %i\n", top[a], i); if(top[a] > -1) //turm ist nicht leer? { // zielturm leer? oder groessere Scheibe? if( (btop == -1) || (btop > -1) && (hanoi[a][atop] < hanoi[b][btop]) ) { hanoi[b][btop+1] = hanoi[a][atop]; hanoi[a][atop] = 0; //nur der Ordnung halber... top[a]--; // quellturm 1 niedriger top[b]++; // zielturm 1 hoeher start = c; //nächstes Mal c zuerst testen. steps++; break; // ausgabe, dann von vorn... } // c leer ODER a kleiner c if( (ctop == -1) || (ctop > -1) && (hanoi[a][atop] < hanoi[c][ctop]) ) { hanoi[c][ctop+1] = hanoi[a][atop]; hanoi[a][atop] = 0; //nur der Ordnung halber... top[a]--; // quellturm 1 niedriger top[c]++; // zielturm 1 hoeher start = b; //nächstes Mal b zuerst testen. steps++; break; // ausgabe, dann von vorn... } } // if turm nicht leer } // for 3 } // while (MAIN loop) return 0; } /* Pauses for a specified number of milliseconds. */ void sleep( clock_t wait ) { clock_t goal; goal = wait + clock(); while( goal > clock() ) ; } -
Das ist ganz einfach, verwende folgenden Code:
def bewege(n, von, ueber, nach): if n==1: print 'Lege eine Scheibe von', von, 'nach', nach,'.' else: bewege(n-1, von, nach, ueber) bewege(1, von, ueber, nach) bewege (n-1, ueber, von, nach) bewege (3,1,2,3) raw_input("Beenden mit <ENTER>") -
leonards schrieb:
Das ist ganz einfach, verwende folgenden Code:
def bewege(n, von, ueber, nach): if n==1: print 'Lege eine Scheibe von', von, 'nach', nach,'.' else: bewege(n-1, von, nach, ueber) bewege(1, von, ueber, nach) bewege (n-1, ueber, von, nach) bewege (3,1,2,3) raw_input("Beenden mit <ENTER>")
könntest du den code erläutern muss nämlich die selbe aufgabe bewältigen und würde das schon gerne verstehen:)
L.G. Alessandro -
rachyy schrieb:
leonards schrieb:
Das ist ganz einfach, verwende folgenden Code:
def bewege(n, von, ueber, nach): if n==1: print 'Lege eine Scheibe von', von, 'nach', nach,'.' else: bewege(n-1, von, nach, ueber) bewege(1, von, ueber, nach) bewege (n-1, ueber, von, nach) bewege (3,1,2,3) raw_input("Beenden mit <ENTER>")
könntest du den code erläutern muss nämlich die selbe aufgabe bewältigen und würde das schon gerne verstehen:)
L.G. Alessandro
Ich kann mal versuchen, den Code zu erläutern, ich habe allerdings keine Ahnung, wofür dieser Überhaupt ist.
Wenn das erste Argument (also n) 1 ist, wird der Text "Lege eine Scheibe von x nach y." angezeigt. (x und y sind natürlich von und nach). In jedem anderen Fall (n ist also ungleich 1) wird die Funktion drei mal aufgerufen. DIe Argumente werden dabei in der Reihenfolge vertauscht. Zusätlich wird bei dem ersten und dritten Aufruf für das neue n das alte n minus 1 angegeben wird.
bewege(3,2,1,3) raw_input("Beenden mit <ENTER>")
In der ersten Zeile dieses Codeabschnitts wird die Funktion bewege (die ja vorher definiert wurde) aufgerufen. Als Argumente werden 3 für n, 1 für von, 2 für über und 3 für nach mitgegeben. Dann wird diese Funktion ausgeführt (und führt sich selber auch noch mehrmals aus). Wenn alles fertig ist, wird der Text "Beenden mit <ENTER>" angezeigt und bei dem Tastendruck von Enter beendet sich das Programm.
Für mehr Informtionen müsste ich aber noch mal erfahren, wofür dieser Code überhaupt da ist. Wenn fragen sind, bitte einfach fragen, ich versuche sie bestmöglichst zu beantworten. -
leonards schrieb:
vielen Danke für die Antwort der code ist für die lösung von Türme von hanoi.
rachyy schrieb:
leonards schrieb:
Das ist ganz einfach, verwende folgenden Code:
def bewege(n, von, ueber, nach): if n==1: print 'Lege eine Scheibe von', von, 'nach', nach,'.' else: bewege(n-1, von, nach, ueber) bewege(1, von, ueber, nach) bewege (n-1, ueber, von, nach) bewege (3,1,2,3) raw_input("Beenden mit <ENTER>")
könntest du den code erläutern muss nämlich die selbe aufgabe bewältigen und würde das schon gerne verstehen:)
L.G. Alessandro
Ich kann mal versuchen, den Code zu erläutern, ich habe allerdings keine Ahnung, wofür dieser Überhaupt ist.
Wenn das erste Argument (also n) 1 ist, wird der Text "Lege eine Scheibe von x nach y." angezeigt. (x und y sind natürlich von und nach). In jedem anderen Fall (n ist also ungleich 1) wird die Funktion drei mal aufgerufen. DIe Argumente werden dabei in der Reihenfolge vertauscht. Zusätlich wird bei dem ersten und dritten Aufruf für das neue n das alte n minus 1 angegeben wird.
bewege(3,2,1,3) raw_input("Beenden mit <ENTER>")
In der ersten Zeile dieses Codeabschnitts wird die Funktion bewege (die ja vorher definiert wurde) aufgerufen. Als Argumente werden 3 für n, 1 für von, 2 für über und 3 für nach mitgegeben. Dann wird diese Funktion ausgeführt (und führt sich selber auch noch mehrmals aus). Wenn alles fertig ist, wird der Text "Beenden mit <ENTER>" angezeigt und bei dem Tastendruck von Enter beendet sich das Programm.
Für mehr Informtionen müsste ich aber noch mal erfahren, wofür dieser Code überhaupt da ist. Wenn fragen sind, bitte einfach fragen, ich versuche sie bestmöglichst zu beantworten.
habe alles so weit verstanden aber eine frage hätte ich noch woher weis das programm wann es zu ende ist?
und wie bist du zu dem code gekommen hast du ihn selbst geschrieben? -
Ich weiß erlich gesagt nicht mehr, ob ich das Programm selber geschrieben habe oder woher ich es habe. Ich denke aber mal das ich das selber zusammen gebsatelt habe...
Das Programm weiß, wann es zu Ende ist, da die Funktion so lange aktiv ist, bis sie sich nicht mehr selber aufruft. Dann ist die Zeile mit bewege(3,2,1,3) oder so was zu Ende. Und da nun mal direkt danach die "Beenden mit <ENTER>"-Zeile folgt, wird die dann aufgerufen. -
leonards schrieb:wird die Funktion drei mal aufgerufen
Aber wieso hört das Programm auf sich selber aufzurufen.
Ach jetzt habe ich es verstanden danke nochmal aber in der konsole werden mir dann acht schritte angezegit wie kann dass sein wenn die funktion nur 3 mal ausgefürt wird?
Beitrag zuletzt geändert: 5.6.2014 21:52:01 von rachyy -
Da die Funktion sich selber aufruft, sobald n ungleich 1 ist, kann es gut sein, das dir acht Schritte angezeigt werden. So rufst du die Funktion ein mal auf und sie selber ruft sich noch drei mal auf. In den dann aufgerufen Funktionen kann sie sixh natürlich nochmals aufrufen...
Nur aus interesse: Kannst du eventuell deinen fertigen Code hier mal schreiben? -
leonards schrieb:
Da die Funktion sich selber aufruft, sobald n ungleich 1 ist, kann es gut sein, das dir acht Schritte angezeigt werden. So rufst du die Funktion ein mal auf und sie selber ruft sich noch drei mal auf. In den dann aufgerufen Funktionen kann sie sixh natürlich nochmals aufrufen...
Nur aus interesse: Kannst du eventuell deinen fertigen Code hier mal schreiben?
Hier mein code ist nicht arg anders als deiner habe schon deinen verwendet aber habe so aktiv nachgefragt da ich einfach nicht nur kopieren möchte sonder auch verstehen was dier code mach und wie er es macht.
Und nochmal danke für die schnellen antworten
L.G Alessandro
def bewege(n, von, ueber, nach): if n==1: print 'Lege einen Stein von Feld', von, 'nach Feld', nach,'.' else: bewege(n-1, von, nach, ueber) bewege(1, von, ueber, nach) bewege (n-1, ueber, von, nach) bewege (3,1,2,3) -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
