Im Jahre 1202 ging Leonardo Pisano (genannt: FIBONACCI) der Frage nach, "wieviele Hasenpaare als Nachkommen eines Ur-Hasenpaares innerhalb eines Jahres zur Welt kommen können". Nehmen wir mal an, jedes Hasenpaar bekommt pro Monat ein Hasenpaar als Nachwuchs. Und jeder Hase ist geschlechtsreif, wenn er einen Monat auf der Welt ist. Außerdem sterben die Hasen natürlich nie ... Nach einem Monat gibt es dann 2 Hasenpaare, nach zwei Monaten 3, nach vier Monaten 5 usw.

Fibonacci schrieb diesen Sachverhalt in folgender Formel auf (die sog. Fibonacci-Zahlen):

F₀ = 0;
F₁ = 1;
   ...
F_n+2 = F_n+1 + F_n (für n >= 0)

Aufgabe 1

Schreiben Sie zwei Oberon-Programme, die jeweils die n.te Fibonacci-Zahl berechnen und ausgeben.
(Einlesen der Zahl n von der Standardeingabe, Ausgabe von F_n auf der Standardausgabe)

a) Verwenden Sie zur Berechnung einen rekursiven Algorithmus            (5 Punkte)
b) Verwenden Sie zur Berechnung einen iterativen Algorithmus              (5 Punkte)

Beispiel:

    thales$ fibit
    Iterative Berechnung der n.Fibonacci-Zahl.
    Geben Sie bitte einen ganzzahligen Wert fuer n ein: 5
    F(5) = 5
    thales$ fibrek
    Rekursive Berechnung der n.Fibonacci-Zahl.
    Geben Sie bitte einen ganzzahligen Wert fuer n ein: 6
    F(6) = 8

Dieses Übungsblatt eignet sich hervorragend dazu, dass sie die Bearbeitung innerhalb Ihrer Gruppe aufteilen!

Hier die Folge der Fibonacci-Zahlen:        0   1   1   2   3   5   8   13   21   34   55   89  144   ....