Schreiben wir Programme, die die Türme von Hanoi in Python und C lösen. Alle geben die Züge aus, mit denen 3 Scheiben vom linken auf den rechten Stab kommen. Der Gedanke steht im Artikel Der Algorithmus der Türme von Hanoi, deshalb geht es hier vor allem um den Code und darum, wie du ihn ausführst.
Mit Rekursion in Python lösen
Das ist die einfachste Form. Sie macht aus „die oberen n − 1 Scheiben beiseite → Scheibe n bewegen → die n − 1 Scheiben zurück“ direkt eine Funktion.
def hanoi(n, src, dst, via, moves):
if n == 0:
return
hanoi(n - 1, src, via, dst, moves) # die oberen n-1 Scheiben beiseite
moves.append((n, src, dst)) # Scheibe n bewegen
hanoi(n - 1, via, dst, src, moves) # die n-1 Scheiben zurück
moves = []
hanoi(3, "links", "rechts", "Mitte", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
print(f"Zug {i}: Scheibe {disc}: {src} -> {dst}")
print(f"insgesamt {len(moves)} Zuege") Speichere es als hanoi.py und führe es mit python3 hanoi.py aus, dann wird Folgendes ausgegeben.
Zug 1: Scheibe 1: links -> rechts
Zug 2: Scheibe 2: links -> Mitte
Zug 3: Scheibe 1: rechts -> Mitte
Zug 4: Scheibe 3: links -> rechts
Zug 5: Scheibe 1: Mitte -> links
Zug 6: Scheibe 2: Mitte -> rechts
Zug 7: Scheibe 1: links -> rechts
insgesamt 7 Zuege Wenn du die 3 in hanoi(3, ...) änderst, löst es jede Scheibenzahl. Die Zahl der Züge ist aber 2ⁿ − 1 und wird deshalb schnell riesig: bei 20 Scheiben etwa eine Million Züge, bei 30 Scheiben etwa eine Milliarde. Python hat eine Obergrenze für die Rekursionstiefe (standardmäßig etwa 1.000 Ebenen), aber die Rekursionstiefe der Türme von Hanoi ist die Scheibenzahl plus 1, sodass die Zahl der Züge lange vorher viel zu groß wird.
Ohne Rekursion in Python lösen
Hier steht das Verfahren fürs Lösen von Hand (die zwei Regeln aus dem Artikel zur Lösungsmethode) direkt als Schleife. Die Stäbe werden mit den Nummern 0 (links), 1 (Mitte) und 2 (rechts) behandelt.
def hanoi_loop(n):
names = ["links", "Mitte", "rechts"]
pegs = [list(range(n, 0, -1)), [], []] # von unten nach oben
order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2] # Reihenfolge, in der 1 wandert
pos = 0 # der Stab mit Scheibe 1 (die wievielte Stelle in order)
moves = []
for m in range(1, 2 ** n):
if m % 2 == 1:
# ungerader Zug: 1 in der festgelegten Richtung zum nächsten Stab
a = order[pos]
pos = (pos + 1) % 3
b = order[pos]
else:
# gerader Zug: bei den zwei Stäben ohne 1 die kleinere auf die größere
a, b = [p for p in range(3) if p != order[pos]]
if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
a, b = b, a
pegs[b].append(pegs[a].pop())
moves.append((pegs[b][-1], names[a], names[b]))
return moves
for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
print(f"Zug {i}: Scheibe {disc}: {src} -> {dst}") Die Ausgabe sind genau dieselben 7 Züge wie bei der rekursiven Fassung. Wir haben geprüft, dass bei jeder Scheibenzahl von 1 bis 10 dieselben Züge herauskommen wie bei der rekursiven Fassung.
Direkt aus dem Binärsystem berechnen in Python
Hier wird berechnet, was in Zug m zu tun ist, ohne die Züge davor durchzugehen. Die Bedeutung der Formeln erklärt der Artikel zum Algorithmus.
def hanoi_bits(n):
for m in range(1, 2 ** n):
disc = (m & -m).bit_length() # Anzahl der Nullen am Ende + 1
src = (m & (m - 1)) % 3
dst = ((m | (m - 1)) + 1) % 3
yield disc, src, dst
print(list(hanoi_bits(3))) Beim Ausführen erscheint [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. Das sind Tripel aus (Scheibe, Ausgangsstab, Zielstab) und entsprechen den 7 Zügen oben. Diese Formel liefert bei ungerader Scheibenzahl die Züge von Stab 0 auf Stab 2 und bei gerader Scheibenzahl von Stab 0 auf Stab 1. Willst du bei gerader Scheibenzahl nach rechts bewegen, vertauschst du Stab 1 und Stab 2.
Mit Rekursion in C lösen
Auch in C ist die Form dieselbe wie in Python.
#include <stdio.h>
static int count = 0;
void hanoi(int n, const char *src, const char *dst, const char *via) {
if (n == 0) return;
hanoi(n - 1, src, via, dst);
count++;
printf("Zug %d: Scheibe %d: %s -> %s\n", count, n, src, dst);
hanoi(n - 1, via, dst, src);
}
int main(void) {
hanoi(3, "links", "rechts", "Mitte");
printf("insgesamt %d Zuege\n", count);
return 0;
} Speichere es als hanoi.c, kompiliere es mit cc -o hanoi hanoi.c und führe es mit ./hanoi aus, dann werden dieselben 7 Züge und „insgesamt 7 Zuege“ ausgegeben wie bei der rekursiven Fassung in Python.
Typische Stolperfallen beim Schreiben
- Die Reihenfolge der Argumente verwechseln: Beim ersten Aufruf vertauschst du den „Hilfsstab“ und den „Zielstab“, beim zweiten Aufruf den „Ausgangsstab“ und den „Hilfsstab“. Wenn du das falsch machst, kommen Züge heraus, die gegen die Regeln verstoßen.
- Die Abbruchbedingung vergessen: Wenn du nicht bei
n == 0(odern == 1) aufhörst, ruft sich die Funktion endlos weiter auf. - So prüfst du es: Übertrage die ausgegebenen Züge auf ein Brett und prüfe, dass kein Zug eine große Scheibe auf eine kleinere legt und dass es 2ⁿ − 1 Züge sind.
