Teile und Herrsche

Es sind n Scheiben unterschiedlichen Durchmessers gegeben, welche geordnet zu einem Turm geschichtet sind, die untere Scheibe ist die größte. Der Turm steht auf einem Anfangsplatz. Unter Verwendung eines Hilfsplatzes soll dieser Turm nun zu einem Zielplatz transportiert werden, wobei verschiedene Regeln einzuhalten sind.

Wenn die Anzahl der Scheiben 1 beträgt, ist die Lösung des Problems trivial. Bei mehr als einer Scheibe läßt sich das Gesamtproblem in drei Teilprobleme zerlegen:

• Transportiere n-1 Scheiben vom Anfangsplatz auf den Hilfsplatz.
• Transportiere die letzte Scheibe vom Anfangsplatz auf Zielplatz.
• Transportiere n-1 Scheiben vom Hilfsplatz auf den Zielplatz.

Bei näherer Betrachtung der Teilprobleme fällt folgendes auf: a) Der 2. Schritt ist trivial und sofort ausführbar.
b) Der 1. und der 3. Schritt sind von der gleichen Art wie das Ausgangsproblem, nur die Anzahl der Scheiben ist um 1 kleiner und die Bedeutung der Plätze hat sich verändert.
Damit hat man für das Gesamtproblem eine rekursive Lösungsvorschrift formuliert.