Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 76
Beispiel 3.7 Fibonacci-Zahlen
ОглавлениеDie Fibonacci-Zahlen sind wie folgt definiert:
f0 = f1 = 1, fi = fi−1 + fi−2 für i > 0
Man erkennt direkt die Umsetzung der informellen Beschreibung unserer idealisierten Kaninchenwelt: fi−1 ist die Anzahl der Kaninchenpaare vor einem Monat (kein Kaninchen stirbt – wie gesagt, eine ideale Kaninchenwelt), und alle Paare, die schon mindestens zwei Monate alt sind, bekommen Nachwuchs, also fi−2 neue Paare.
Als applikativer Algorithmus schreibt sich die Definition wie folgt:
| fib(x) | = | if (x = 0) ∨ (x = 1) then 1 |
| else fib(x − 2) + fib (x − 1) fi |
Die Bedeutung ist wieder einfach festzulegen:
Da die Auswertung der Fibonacci-Zahlen bereits für kleine Zahlen sehr aufwendig wird und die Ergebnisse exponentiell wachsen, wird uns diese Funktion noch öfter als Beispiel für rekursives Verhalten begegnen.
Die bisherigen Beispiele waren von eher mathematischem Interesse. Das folgende Beispiel ist für die Informatiksichtweise interessant: Nehmen wir an, wir hätten einen Rechner, der nur die Addition beherrscht. Wie können wir trotzdem eine Multiplikation realisieren? Derartige Fragestellungen spielen bei der Umsetzung von Programmen auf einfachere Hardware eine wichtige Rolle.
