Die Webseiten der Fachschaft Informatik am ERG Saalfeld


Türme von Hanoi

Es wird hier davon ausgegangen, dass die "Spielregeln" bekannt sind. Als Lösung für die Türme von Hanoi wird üblicherweise der Randoffsche Algorithmus verwendet. Im Pseudecode ist das in der Wikipedia dort so angegeben:

funktion bewege (Zahl i, Stab a, Stab b, Stab c) {
    falls (i > 0) {
       bewege(i-1, a, c, b);
       verschiebe oberste Scheibe von a nach c;
       bewege(i-1, b, a, c);
    }
}

Dabei wird der Turm von Stab a über den Hilfsstab b nach Stab c bewegt.
 

Für einen Turm mit 5 Scheiben, der von Stab a nach Stab c bewegt werden soll, bedeutet das:


Bewege den Turm, aber ohne die letzte Scheibe, von Stab a nach Stab b und verwende als Hilfsstab c.


Transportiere nun die große Scheibe von Stab a nach Stab c.


Bewege nun den (kleinen) Turm von Stab b nach Stab c.

Das Bewegen des kleinen Turms mache genauso (Rekursion!)
 

Der Pseudocode lässt sich fast 1:1 in Python umsetzen. Das Programm sieht so aus:

Programm

def bewege (anzahl,stab_a,stab_b,stab_c):
  if anzahl > 0:
      bewege(anzahl-1,stab_a,stab_c,stab_b)
      print('verschiebe oberste Scheibe von ',stab_a,' nach ',stab_c)
      bewege(anzahl-1,stab_b,stab_a,stab_c)

bewege(3,'Turm A','Turm B','Turm C')

 

Der Aufruf sah bei mir so aus:

 

Aufgaben

  1. Bringen Sie das Programm zum Laufen.
  2. Testen Sie das Programm mit verschiedenen Anzahlen von Scheiben.
  3. Ergänzen Sie das Programm um eine Überschrift (unterstrichen, usw.).
  4. "Spielen" Sie dieses Spiel mit 2€, 1€, 5ct, 2ct und 1ct (oder 2€, 50ct, 20ct, 10ct und 2ct).
  5. Ändern Sie das Programm so ab, dass die Anzahl der Scheiben als Parameter übergeben wird.
  6. Informieren Sie sich in der Wikipedia zu Türme von Hanoi
  7. Youtube: Vorlesung von Prof. Dr. Oliver Vornberger an der Universität Osnabrück zu Türme von Hanoi. (1:42 Min).

 

zurück


© ERG Saalfeld   -   HD. Kirmse + Dustin Wiese   14.08.2022