Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 38

Modul Turmbewegung(n, Quelle, Senke, AB)

/* Bewegt einen Turm der Höhe n von Quelle

nach Senke unter Benutzung des Arbeitsbereichs */

falls n = 1

dann bewege Scheibe von Quelle zur Senke

sonst Turmbewegung(n-1, Quelle, AB, Senke)

bewege 1 Scheibe von Quelle zur Senke

Turmbewegung(n-1, AB, Senke, Quelle)

Rekursives Verfahren

Das Prinzip besagt Folgendes: Möchte ich einen Turm der Höhe 5 von A nach B bewegen (unter Zuhilfenahme von C), kann ich das damit erreichen, dass ich einen Turm der Höhe 4 erst von A nach C bewege (jetzt unter Zuhilfenahme von B), dann die größte, fünfte Scheibe direkt nach B lege und den Turm der Höhe 4 zuletzt von C nach B auf diese Scheibe bewege. Das Verfahren heißt rekursiv, da sich eine Turmbewegung (der Größe n) unter anderem wiederum durch zwei Turmbewegungen (nun der Höhe n − 1) beschreiben lässt.

Abb. 2–4 Türme von Hanoi

Der folgende Ablauf verdeutlicht die Vorgehensweise (genauer in Abbildung 2–4). Ziel ist eine Bewegung eines Turmes der Höhe 3 von A nach B. Die Rekursion wird durch Einrückungen verdeutlicht. Es werden nur die Aufrufe der Turmbewegungen (als Turm abgekürzt) und die Scheibenbewegungen notiert.

Turm(3,A,B,C)

Turm(2,A,C,B)

Turm(1,A,B,C)

bewege A → B

bewege A → C

Turm(1,B,C,A)

bewege B → C

bewege A → B

Turm(2,C,B,A)

Turm(1,C,A,B)

bewege C → A

bewege C → B

Turm(1,A,B,C)

bewege A → B

Bei 64 Scheiben benötigt man übrigens ca. 600.000.000.000 Jahre, falls man jede Sekunde eine Scheibe bewegen kann (genauer: 2⁶⁴ − 1 Sekunden!).

Module als aufrufbare Programme

Das Beispiel zeigte noch eine weitere Besonderheit: Der beschriebene Pseudocode-Algorithmus hat sich quasi selbst als Unterprogramm aufgerufen. Das Schlüsselwort Modul startet die Definition eines derartig aufrufbaren Unterprogramms, indem nach ihm der Name des Unterprogramms und eventuelle Parameter für den Aufruf festlegt werden.