kostenloser Webspace werbefrei: lima-city


Hanoi Turm Problem iterativ lösen

lima-cityForumProgrammiersprachenPython

  1. Autor dieses Themas

    lordcodex

    Kostenloser Webspace von lordcodex

    lordcodex hat kostenlosen Webspace.

    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
  2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

  3. g****e

    Deine Hausaufgaben machen ist doof :-P

    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
  4. Autor dieses Themas

    lordcodex

    Kostenloser Webspace von lordcodex

    lordcodex hat kostenlosen Webspace.

    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 -.-
  5. g****e

    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
  6. Autor dieses Themas

    lordcodex

    Kostenloser Webspace von lordcodex

    lordcodex hat kostenlosen Webspace.

    Check noch nicht so ganz wie ich es speichern soll das alle, oder nur teile von einem Turm zum anderen verschoben wurden :/
  7. hackyourlife

    Moderator Kostenloser Webspace von hackyourlife

    hackyourlife hat kostenlosen Webspace.

    lordcodex schrieb:
    Check noch nicht so ganz wie ich es speichern soll das alle, oder nur teile von einem Turm zum anderen verschoben wurden :/
    Ich geb dir mal eine Java-Klasse (Python kann ich leider nicht) für einen Turm, vllt hilfts dir zum Verstehen:
    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
  8. Autor dieses Themas

    lordcodex

    Kostenloser Webspace von lordcodex

    lordcodex hat kostenlosen Webspace.

    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() )
          ;
    }
  9. 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>")
  10. 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
  11. 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.
  12. leonards schrieb:
    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.
    vielen Danke für die Antwort der code ist für die lösung von Türme von hanoi.

    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?
  13. 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.
  14. 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
  15. 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?
  16. 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)
  17. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

    lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

Login zum Webhosting ohne Werbung!