Logo des digitalen Schulbuchs o-mathe.de. Schriftzug mit Omega als O

Minimallogo des digitalen Schulbuchs inf-schule.de. Omega als Symbol

s n h m r u
i

Ein Lösungsverfahren

Zielsetzung

Wir haben bereits eine Strategie entwickelt, wie man Türme beliebiger Höhe umschichtet. Auf dieser Seite geht es darum, diese Strategie als ein Lösungsverfahren (man nennt das einen Algorithmus) zu formulieren. Außerdem wird die dahinter liegende Idee vertieft. Für die weitere Bearbeitung des Kapitels ist diese Seite nicht erforderlich.

Auf eine Lösung zurückgreifen

Wir betrachten das Umschichtungsproblem für $n = 5$ Scheiben.

Problem: Transportiere einen 5-Scheiben-Turm von A über B nach C.

Eine Löseverfahren könnte so aussehen:

Türme von Hanoi - Anfangszustand
Transportiere einen 4-Scheiben-Turm von A über C nach B.
Türme von Hanoi - Zwischenzustand
Transportiere eine Scheibe von A nach C.
Türme von Hanoi - Zwischenzustand
Transportiere einen 4-Scheiben-Turm von B über A nach C.
Türme von Hanoi - Endzustand

Aufgabe 1

Die Lösung zum Ausgangsproblem weist eine Besonderheit auf. Sie beschreibt nicht jeden einzelnen Scheibentransport. Die Lösung besteht vielmehr darin, das Ausgangsproblem auf ein entsprechendes Problem in verkleinerter Form zu reduzieren. Man nennt diese Strategie rekursive Problemreduktion.

Erläutere diese Problemlösestrategie am Beispiel "Transportiere einen 5-Scheiben-Turm von A über B nach C".

Ein Löseverfahren für die Türme von Hanoi allgemein formulieren

Wir beschreiben das Problem zunächst verallgemeinernd.

Problem: Transportiere einen n-Scheiben-Turm 
    von einem Ausgangsstapel X 
    über einen Hilfsstapel Y 
    zu einem Zielstapel Z.

Die oben beschriebene Lösungsidee wird jetzt zu einem Lösungsalgorithmus verallgemeinert.

ALGORITHMUS transportiere einen n-Scheiben-Turm von X über Y nach Z:
    wenn n > 1:
        transportiere einen (n-1)-Scheiben-Turm von X über Z nach Y
        transportiere eine Scheibe von X nach Z
        transportiere einen (n-1)-Scheiben-Turm von Y über X nach Z
    sonst:
        transportiere eine Scheibe von X nach Z 

Hier sind n, X, Y und Z Parameter, die bei konkreten Problemstellungen aktualisiert werden müssen.

Aufgabe 2

Dass der Algorithmus tatsächlich das allgemeine Umschichtungsproblem löst, zeigt sich, wenn man sämtliche Schritte ausführt.

Verdeutliche das am Beispiel eines 3-Scheiben-Turms. Erkläre hierzu die folgendenden Ausführungen.

Ausführungstiefe 1:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C

Ausführungstiefe 2:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B:
        transportiere einen 1-Scheiben-Turm von A über B nach C
        transportiere eine Scheibe von A nach B
        transportiere einen 1-Scheiben-Turm von C über A nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C:
        transportiere einen 1-Scheiben-Turm von B über C nach A
        transportiere eine Scheibe von B nach C
        transportiere einen 1-Scheiben-Turm von A über B nach C

Ausführungstiefe 3:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B:
        transportiere einen 1-Scheiben-Turm von A über B nach C:
            transportiere eine Scheibe von A nach C
        transportiere eine Scheibe von A nach B
        transportiere einen 1-Scheiben-Turm von C über A nach B:
            transportiere eine Scheibe von C nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C:
        transportiere einen 1-Scheiben-Turm von B über C nach A:
            transportiere eine Scheibe von B nach A
        transportiere eine Scheibe von B nach C
        transportiere einen 1-Scheiben-Turm von A über B nach C:
            transportiere eine Scheibe von A nach C

Wenn man jetzt alle Aufrufe des Algorithmus weglässt, dann ergibt sich eine Folge von Basisaktionen, die letztlich das Problem löst.

            transportiere eine Scheibe von A nach C
        transportiere eine Scheibe von A nach B
            transportiere eine Scheibe von C nach B
    transportiere eine Scheibe von A nach C
            transportiere eine Scheibe von B nach A
        transportiere eine Scheibe von B nach C
            transportiere eine Scheibe von A nach C

Suche

v
1.2.1.2.1.6
o-mathe.de/grundlagen/folgen/folgenkonzept/tuermevonhanoi/lernstrecke/algorithmus
o-mathe.de/1.2.1.2.1.6

Rückmeldung geben