Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 14. November 2002
Christian Ehrhardt Blatt 5






Allgemeine Informatik 3 (WS 2002/2003)


Abgabetermin 25.11.2002

Rekursive Teppiche

Für dieses Übungsblatt ist ein Teppich ein quadratisches Muster aus verschiedenen Zeichen, das wie folgt rekursiv definiert ist:

• Ein Teppich der Seitenlänge 0 ist leer (was sonst).
• Ein Teppich der Seitenlänge 1 besteht nur aus dem Zeichen ``*''.
• Alles weitere spielt nur eine Rolle, wenn die Seitenlänge des Teppichs größer als 1 ist.
• Wenn die Seitenlänge des Teppichs nicht durch 3 teilbar ist, besteht der Teppich aus zwei Teilen: Einem Rahmen bestehend aus dem Zeichen ``#'' und einem Teppich mit einer um zwei verkleinerten Seitenlänge in der Mitte.
• Wenn die Seitenlänge des Teppichs durch 3 teilbar ist, wird die Fläche des Teppichs in 9 gleich große Quadrate aufgeteilt. Das mittlere wird weiß, die anderen 8 Quadrate sind wieder Teppiche (deren Seitenlänge nur ein Drittel so groß ist).

Beispiel

Ein Teppich der Seitenlänge 15 besteht, da 15 durch 3 Teilbar ist aus einem weißen Quadrat der Seitenlänge 5, das von 8 Teppichen der Seitenlänge 5 umgeben ist. Im linken Bild sieht man das weiße Quadrat in der Mitte und die 8 Teilteppiche mit unterschiedliche Zahlen markiert. Da Teilteppich 1 (links oben) die Seitenlänge 5 hat, die nicht durch 3 teilbar ist besteht er aus einem Teppich der Länge 3 in der Mitte und einem Rahmen aus dem Zeichen ``#''. Das ist im zweiten Bild bereits für alle 8 Teilteppiche erledigt. Jeder der Teilteppiche hat jetzt noch die Seitenlänge 3 und besteht damit aus einem weißen Quadrat mit Seitenlänge 1, das von 8 Teppichen der Seitenlänge 1 umgeben ist. Ein Teppich der Seitenlänge 1 besteht nur aus dem Zeichen ``*'', daher sieht der fertige Teppich aus wie im dritten Bild.

Aufgabe

Ihr sollt ein Programm schreiben, das solche Teppiche mit einer Seitenlänge bis zu 500 auf dem Bildschirm ausgeben kann. Die Seitenlänge soll von der Tastatur eingelesen werden.

Hinweise

• Der Teppich sollte zunächst in einem globalen zweidimensionalen Array konstruiert werden. Erst wenn das fertig ist kann er ausgegeben werden. Das hat den Vorteil, daß Veränderungen an beliebigen Stellen der späteren Ausgabe gemacht werden können. Wenn direkt auf den Bildschirm ausgegeben werden würde müßte Zeilenweise gearbeitet werden.
• Die Hauptarbeit erledigt eine rekursive Prozedur build, die Teppiche beliebiger Größe an beliebigen Stellen in dem globalen Array konstruieren kann. Diese Prozedur wird drei Parameter benötigen: Zwei, die eine Ecke des Teppichs angeben und die Seitenlänge. Außerdem ist zu erwarten, daß sie sich selbst an mehreren Stellen rekursiv aufruft um kleinere Teppiche zu konstruieren.
• Um tatsächlich auch größere Muster auf dem Bildschirm sehen zu können kann die Schriftgröße des Terminals auf unseren Suns mit Ctrl-Rechte Maustaste auf Unreadable gestellt werden.
• Der Teppich mit Seitenlänge 499 sieht interessanter aus als der mit Seitenlänge 500.