Suche Home Einstellungen Anmelden Hilfe  

Standardalgorithmen
 
  
Anfang
vor
  

2.2 Die Türme von Hanoi

2.2.1 Die Spielregeln

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. 
  • Es darf stets nur eine Scheibe, und zwar die oberste eines Turmes bewegt werden.
  • Zu keiner Zeit darf eine größere Scheibe auf einer kleineren liegen.
 
 
Anfangsplatz Zielplatz
 
Hilfsplatz
 
 
 
     
         
 
Schritt 1
1 -> 2
     
 
           
 
Schritt 2
1 -> 3
 
                       
   
Schritt 3
2 -> 3
 
 
                 
 
Schritt 4
1 -> 2
 
 
               
 
Schritt 5
3 -> 1
 
                 
 
Schritt 6
3 -> 2
     
 
           
 
Schritt 7
 
1 -> 2
     
 
         
 
  
Anfang
vor
zurück
  

2.2.2 Die Lösung

Die Aufgabe läßt sich kurz folgendermaßen formulieren: 
    Transportiere n Scheiben vom Anfangsplatz  auf den Zielplatz, verwende einen Hilfsplatz.
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. 
 

  
Anfang
vor
zurück
  

2.2.3 Die Behandlung im Unterricht

Zuerst sollte die Frage stehen, ob dieses Problem überhaupt im Unterricht behandelt werden soll. Für den Leistungskursbereich läßt sich diese Frage sicherlich ohne weiteres mit ja beantworten. 
Für einen Grundkurs sieht das schon ganz anders aus. Im Rahmenplan wird gefordert, daß der Schüler einfache Algorithmen entwickeln kann, die Türme von Hanoi gehören sicherlich nicht dazu. Wenn dieses Problem also überhaupt im Grundkurs behandelt wird, dann wird der  Lehrer mit großer Sicherheit wesentliche Teile der Lösung vorgeben müssen. Es ist daher schon als Erfolg zu werten, wenn die Schüler erkennen, daß eine Rekursion vorliegt. 
Wenn die Lösung als Programm vorliegt, ist es für die Schüler sicherlich verblüffend, wie ein schwierig anmutendes Problem sich auf diese einfache und elegante Art und Weise lösen läßt. 
 
  
Anfang
vor
zurück
  

2.2.3.1 Die grafische Darstellung der Schritte

Nach der Bekanntgabe der Spielregeln sollte man die Schüler zuerst einmal spielen lassen. Für eine geringe Anzahl an Scheiben (maximal 4) stellen dann die Schüler ihre Lösungen vor. Um auf die angestrebte Zerlegung zu kommen, ist es sinnvoll, die Lösungen für 2 bis 4 Scheiben grafisch darzustellen. Dabei sollten die Scheiben so farbig dargestellt werden, daß jeweils die untere Scheibe eine neue Farbe bekommt. 
 
 
  
Türme von Hanoi, gespielt mit zwei Scheiben
(drei Schritte)
 
 
Türme von Hanoi, gespielt mit drei Scheiben
(sieben Schritte)
 
 
 Türme von Hanoi, gespielt mit vier Scheiben
(fünfzehn Schritte)
 
Für dieses Dokument wurde in den Folien der weisse Hintergrund durch die Hintergrundfarbe in diesem Dokument ersetzt. Für die Verwendung der Folien im Unterricht kann diese Änderung  wieder rückgängig gemacht werden. 
 
  
Anfang
vor
zurück
  

2.2.3.2 Die sprachliche Formulierung der Lösung

Ziel der Sprachlichen Formulierung ist eine Schrittfolge, wie sie bereits im Abschnitt 2.2.2 dargestellt wurde. Nachdem die Folien mit den Schülern ausgewertet wurden, ist sicherlich eine solche Schrittfolge nicht auf Anhieb zu erwarten. 

Der entscheidende Hinweis ist sicherlich, daß das Bewegen von n-1 Scheiben auch als ein Schritt gilt. Dann kommt es nur noch darauf an, die Bedeutung der Plätze richtig zuzuordnen. Das läßt sich mit Hilfe der Folien für zwei und drei Scheiben nachvollziehen. Es ergibt sich folgende Schrittfolge: 
 

    Bewege drei Scheiben von Platz 1 nach Platz 2 (Hilfsplatz ist Platz 3) 
      Bewege zwei Scheiben von Platz 1 nach Platz 3 (Hilfsplatz ist Platz 2) 
        Bewege eine Scheibe von Platz 1 nach Platz 2 
        Bewege eine Scheibe von Platz 1 nach Platz 3 
        Bewege eine Scheibe von Platz 2 nach Platz 3
      Bewege eine Scheibe von Platz 1 nach Platz 2 
      Bewege zwei Scheiben von Platz 3 nach Platz 2 (Hilfsplatz ist Platz 1) 
        Bewege eine Scheibe von Platz 3 nach Platz 1 
        Bewege eine Scheibe von Platz 3 nach Platz 2 
        Bewege eine Scheibe von Platz 1 nach Platz 2
Hieraus läßt sich jetzt gemeinsam mit den Schülern die allgemeine Schrittfolge erarbeiten. 
 
  
Anfang
vor
zurück
  

2.2.3.3 Das Struktogramm

 
  
Anfang
vor
zurück
  

2.2.3.4 Das Programm

Für die Türme von Hanoi läßt sich jetzt die folgende rekursive Prozedur formulieren: 
    procedure turm(ap,zp,hp,n:byte); 
    begin 
      if n=1 then  
        writeln(' Scheibe von Platz ',ap,' auf Platz ',zp)
              else begin 
              turm(ap,hp,zp,n-1); 
              writeln(' Scheibe von Platz ',ap,' auf Platz ',zp); 
              turm(hp,zp,ap,n-1);
         end; 
    end;
Bedeutung der Variablen: 
    ap - Anfangsplatz 
    zp - Zielplatz 
    hp - Hilfsplatz 
    n   - Anzahl der Scheiben 
     
Die Übergabe des Hilfsplatzes als Parameter kann auch entfallen, wenn man als Berechnung einsetzt: 
    hp := 6 - ap - zp.
Für die Behandlung im Unterricht ist das aber nicht empfehlenswert. 

vollständiges Programm 
(TPW 1.5 für Windows; Dateiname: hanoi.pas) 
 
 

  
Anfang
zurück
  

2.2.4 Mögliche Weiterentwicklungen

Bei der Lösung, welche im Abschnitt 2.2.3.4 dargestellt wurde, habe ich auf eine grafische Darstellung der Schritte bewußt verzichtet. Erstens ist mit der TurboPascal Version 1.5 für Windows Grafik nur möglich mit Hilfe der objektorientierten Programmierung und zweitens würde diese Variante sehr viel Zeit beanspruchen, ohne das die Schüler sich mit Rekursion beschäftigen. 

Für Interessierte an dieser Stelle trotzdem noch einmal eine Lösung mit Grafik: 

Programm 
(TP 5.0 für DOS; Dateiname: hanoigr.pas) 

Wer rekursiv weiterarbeiten möchte, dem empfehle ich die Berechnung der Schritte für eine bestimmte Anzahl von Scheiben. Die Funktion sieht folgendermaßen aus: 

function schritte(n:byte):longint; 
begin 
     if n=1 then schritte:=1 
     else schritte:=2*schritte(n-1)+1 
end; 
 
 

  
Anfang
  
 

Benutzer: Gast • Besitzer: seminar • Zuletzt gešndert am: