Prof. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 15. November 2004
Christian Ehrhardt Blatt 4






Allgemeine Informatik 3 (WS 2004/2005)


Abgabetermin 23.11.2004

Ein fast Pascal'sches Dreieck (10 Punkte)

Das Pascal'sche Dreieck dürfte jeden als Hilfmittel zur Berechnung der Koeffizienten einer Binomischen Formel bekannt sein. Interessant ist, daß sich die jeweils nächste Zeile des Dreiecks alleine aus der vorhergehenden Zeile berechnen läßt.
Im folgenden betrachten wir ein Dreieck, bei dem sich ebenfalls die nächste Zeile aus der vorhergehenden berechnen läßt. Genau wie beim Pascal'schen Dreieck besteht die erste Zeile nur aus einem einzigen Zeichen, der Ziffer 1. Ist eine Zeile gegeben, so berechnet sich die nächste Zeile wie folgt:

• Die alte Zeile wird in Gruppen aufeinanderfolgender Zeichen aufgeteilt, so daß alle Zeichen einer Gruppe gleich sind (dabei soll natürlich die Zahl der entstehenden Gruppen minimal sein, d.h. zwei aufeinanderfolge gleiche Zeichen müssen zur selben Gruppe gehören).
• Die neue Zeile ergibt sich indem man die Gruppen von links nach rechts betrachtet und für jede Gruppe zuerst deren Größe und anschließend das (einzige) in Ihr vorkommende Zeichen notiert. Die auf diese Weise notierten Zeichen bilden die nächste Zeile.

Schreibt ein Programm, das die ersten N Zeilen dieses Dreiecks berechnen kann. So könnte der Beginn der Ausgabe aussehen:

   1
   11
   21
   1211
   111221
   312211
   13112221
   1113213211

Hinweis

Man kann zeigen, daß in diesem Dreieck nur die Zeichen 1, 2 und 3 vorkommen können.