Die Türme von Hanoi

Ein besonders schönes Beispiel für elegante Programmierung ist das Problem der Türme von Hanoi.

Auftrag 1:

Studiere die Seiten 1 und 2 in der PDF-Datei zum Problem.

Das Programm zur Lösung des Problems ist in rekursiver Formulierung in nur wenigen Zeilen formuliert. Der eigentliche Algorithmus besteht letztlich nur aus vier Zeilen.

 class Hanoi
{ int starthoehe;
  int bewegungen = 0;
  SimpleInput in;

  void bewege(char von, char nach)
  { System.out.println("Scheibe von " + von + " nach " + nach);
    bewegungen++;
  }

  void turm(char start, char ziel, char ablage, int hoehe)
  { if (hoehe>1) turm(start, ablage, ziel, hoehe-1);
    bewege(start, ziel);
    if (hoehe>1) turm(ablage, ziel, start, hoehe-1);
  }

  public Hanoi()
  {  in = new SimpleInput();
     starthoehe = in.getInt("Wie hoch soll der \"Turm von Hanoi\" sein? ");
     System.out.println("Die Ausgabe fuer einen \"Turm von Hanoi\"" +
                 " der Hoehe " + starthoehe + ".");
     System.out.println("Die Staebe sind mit A, B und C bezeichnet.");
     System.out.println("Der Turm soll von A nach C transportiert werden.");
     turm('A', 'C', 'B', starthoehe); // von A nach C ueber B
     System.out.println("Es waren " + bewegungen +
                 " Bewegungen fuer die Turmhoehe "
                 + starthoehe + " noetig.");
  }
} // class Hanoi

Auftrag 2:

In der Datei TuermeVonHanoi.zip ist ein fertiges und direkt lauffähiges BlueJ-Projekt gespeichert. Entpacke bzw. extrahiere in ein Verzeichnis und starte das Programm. Mache dir die Ausgabe an einfachen Türmen mit den Höhen 2 und 3 klar.

Aufgabe 3:

Untersuche mit dem Programm die Anzahl der Scheibenbewegungen a(n) in Abhängigkeit von der Turmhöhe n. Gib die Werte hier in der Tabelle ein:

Aufgabe 4:

Man erkennt schnell, dass die Zahlen a(n) nach einer einfachen Formel berechnet werden können. Hinweis: Vergleiche a(n) mit den 2er-Potenzen 2¹, 2², 2³, 2⁴...
Gib die Formel an (Man kann Exponenten so angeben: 5² = 5^2), berechne damit a(64) und die benötigte Zeit.