Hintergrundwissen
Die Fibonacci-Zahlen
Fibonacci-Zahlen (0,1,1,2,3,5,8,...) nennt man die rekursiv definierten natürlichen Elemente der Fibonacci-Folge. Die Fibonacci-Zahlen spielen in verschiedenen Gebieten der Mathematik eine Rolle.
Definition: Die Fibonacci-Folge ist für n>1 rekursiv definiert durch: fn = fn-1 + fn-2, mit den Anfangswerten f0=0 und f1=1.
Die Fibonacci-Zahlen: die ersten Fibonacci-Zahlen lauten: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
(A000045)
# Eine Liste mit den ersten 1000 Fibonacci-Zahlen findet man hier
# Der Online-Rechner ist auch ein Fibonacci-Zahlen-Rechner, zum Beispiel:
Geschichte der Fibonacci-Zahlen: Die Fibonacci-Folge ist benannt nach L.PISANO, genannt FIBONACCI (Kurzform für filius BONACCI), der 1202 in der Liber abbaci, einem mittelalterlichen Mathematikbuch eine Aufgabe beschrieb, in der ein Kanninchenzüchter herausfinden will, wie viele Kaninchenpaare innerhalb eines Jahres aus einem einzigen Paar entstehen, wenn jedes Paar ab dem zweiten Lebensmonat ein weiteres Paar pro Monat zur Welt bringt. Die Gesamtpopulation der Kanninchenpaare des nächsten Monats (fn) ist also die Population des letzten Monats (fn-1) plus Neugeborene. Die Anzahl der Neugeborenen entspricht der Population des vorletzen Monats (fn-2), wir erhalten also eine Fibonacci-Folge als Lösung.
Algorithmen zur numerischen Berechnung der Fibonacci-Zahlen: Die Definition der Fibonacci-Zahlen legt es zunächst nahe, eine rekursive Funktion zu schreiben:
function fibonacci_rekursiv(n)
IF n<2 THEN
return n
ELSE
return fibonacci(n-1)+fibonacci(n-2)
END
Davon ist abzuraten. Die beiden inneren Funktionsaufrufe fibonacci(n-1) und fibonacci(n-2) werden unabhängig voneinander ausgeführt. Viele Berechnungen werden daher mehrfach ausgeführt. Für die Laufzeit des Funktionsaufrufes gilt offenbar: tn > tn-1 + tn-2. Die Laufzeit wächst exponentiell mit der Komplexität des Algorithmus.
Wenn man die Fibonacci-Zahlen von Hand ermittelt, bildet man direkt die Summe der beiden vorherigen Fibonacci-Zahlen. Dies sieht dann so aus:
function fibonacci_iterativ(n)
IF n<2 THEN return n END
f2=0, f1=1
FOR i=2...n
fn = f1 + f2,
f2 = f1,
f1 = fn
NEXT
return fn
Die Laufzeit dieser Funktion ist proportianal zu n. Einen noch schnelleren Algorithmus erhält man, wenn man die Binärdarstellung natürlicher Zahlen verwendet und spezielle Eigenschaften der Fibonacci-Zahlen berücksichtigt.
Fibonacci-Zahlen und der goldene Schnitt: sei φ = 1/2*(1 + √5), dann gilt:
fn = 1/√5 (φn - (-1)n φ-n) (*)
Und da der letzte Term < 1/2 kann man mit Runden die n-te Fibonacci-Zahl auch direkt berechnen:
fn = runden(φn/√5)
Weiter folgt aus (*) auch, dass das Verhältnis zweier aufeinander folgender Fibonacci-Zahlen gegen den goldenen Schnitt konvergiert:
fn+1/fn --> φ
Der Quotient aufeinander folgender Fibonacci-Zahlen und die Kettenbruchdarstellung: Das Verhältnis zweier aufeinander folgender Fibonacci-Zahlen hat eine interessante Kettenbruchdarstellung:
fn+1/fn = [1,1,.....,1] mit genau n Einsen.
Zum Beispiel:
