Programmieren–Wintersemester 2013/14 23.12.2013 – 13:00
encircling the foot of the pyramid and the smallest its top.
And Brahma said unto the priests: „Transfer these sixty-four rings from the first pyramid to the third, transposing
one ring at a time only,and putting it either on a vacant pyramid or on a larger ring. By the time you have
executed this task the end of the world will be near.“
2
A.1
Ein Stapel „Irgendwas“
Ein Stack ist eine Datenstruktur, mit der man einen abstrakten Stapel modelliert. Ein Stack hat zwei klassische
Methoden, davon heißt eine
push
, diese „legt“ ein neues Objekt auf den Stapel. Die andere heißt
pop
und
„nimmt“ das oberste Element vom Stapel und liefert es zurück.
3
Laden Sie sich das generische Interface
Stack
von der Homepage herunter, und implementieren Sie es in der generischen Klasse
DefaultStack
. Verwenden
Sie bei der Implementierung eine Datenstruktur ähnlich der Datenstruktur “Liste” aus der Vorlesung (d.h. eine
rekursive Datenstruktur) und verwenden Sie keine Arrays oder fertige Datenstrukuren aus
java.util
. Das
Charakteristikum eines
Stacks
ist, dass man jeweils nur Zugriff auf das
oberste
Element hat. Achten Sie im
weiteren Verlauf der Implementierung darauf, dieses charakterische Merkmal nicht aufzuweichen.
A.2
Ein Stapel Hanoi-Scheiben
Schreiben Sie die Klassen
HanoiDisk
und
HanoiStack
. Ein
HanoiStack
ist ein spezieller
DefaultStack
, der
HanoiDisks
stapelt. Jede
HanoiDisk
hat eine Breite. Ein
HanoiStack
stapelt nur kleinere auf größere Scheiben
und verbietet das Stapeln von größeren auf kleinere bzw. gleich großen Scheiben.
A.3
Das Hanoi-Problem
Zur Verallgemeinerung und Abstraktion des eingangs zitierten Problems betrachten wir jetzt
3
Stapel von
Hanoi-Scheiben: Stapel
, Stapel
und Stapel
. In der Anfangskonfiguration befinden sich
n
Scheiben aufein-
anderfolgender Breite auf Stapel
und die anderen beiden Stapel sind jeweils leer. Das Ziel ist, alle Scheiben
auf Stapel
zu versetzen, und zwar so, dass pro Zug genau eine Scheibe bewegt wird und zu jedem Zeitpunkt
die Hanoi-Bedingung eingehalten wird, also keine größere Scheibe auf einer kleineren Scheibe zu liegen kommt.
Das Problem lässt sich rekursiv lösen. Vollziehen Sie die Schritte im Pseudocode aus Abbildung A.3 nach oder
machen Sie sich im Netz schlau. Implementieren Sie den Algorithmus und verwenden Sie dabei drei Objekte
der Klasse
HanoiStack
A.3.1
Eingabe
Schreiben Sie für das Hauptprogramm eine Klasse
TowersOfHanoi
. Das Programm soll als Kommandozeilen-
Parameter die Anzahl
n
der Scheiben annehmen, die Datenstrukturen entsprechend initialisieren und den
Lösungs-Algorithmus ablaufen lassen.
A.3.2
Ausgabe
Geben Sie die Anfangskonfiguration, die Konfiguration nach jedem Zwischenschritt und die Zielkonfiguration
auf der Konsole aus. Dabei wird eine Scheibe der Breite
b
mit
2
b
1
Rauten (’
#
’) dargestellt. Die Scheiben
werden pro Turm zentriert und zeilenweise von oben nach unten ausgegeben. Die drei Türme
,
und
stehen
in der Reihenfolge nebeneinander. Jeder Turm nimmt zu jedem Zeitpunkt den Raum von
2
n
1
Zeichen ein und
ist durch ein Leerzeichen von seinem Nachbarturm getrennt. Trennen Sie aufeinanderfolgende Konfigurationen
durch eine Zeile die drei Bindestriche (’
---
’) enthält
