Ein besonders schönes Beispiel für elegante Programmierung ist das Problem der Türme von Hanoi.
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
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.
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:
Man erkennt schnell, dass die Zahlen a(n) nach einer einfachen Formel berechnet werden können. Hinweis: Vergleiche a(n) mit den 2er-Potenzen 21, 22, 23, 24... Gib die Formel an (Man kann Exponenten so angeben: 52 = 5^2), berechne damit a(64) und die benötigte Zeit.