Fibonacci Rechner
Gib eine Position n ein und erhalte F(n), die n-te Fibonacci-Zahl — die Folge, die mit 0, 1 beginnt und jedes Glied aus den beiden davor bildet.
Ein Index, eine Antwort
Gib die Position n ein und der Rechner liefert F(n) — zum Beispiel F(10) = 55, das zehnte Glied, gezählt ab F(0) = 0.
Exakt bis F(78)
Ab F(78) werden die Werte größer, als ein Computer sie exakt speichern kann, deshalb gibt der Rechner oberhalb von Index 78 kein Ergebnis statt eines gerundeten aus.
Was ist ein Fibonacci-Rechner?
Index rein, Fibonacci-Zahl raus
Ein Fibonacci-Rechner macht aus einer einzigen Position — dem Index n — die Zahl F(n), die an dieser Stelle in der berühmten Fibonacci-Folge steht. Die Folge beginnt mit 0, 1 und addiert dann immer die beiden jüngsten Glieder: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 und weiter. Da jedes Glied feststeht, sobald du die beiden davor kennst, verrät dir allein der Index den Wert. Das macht dieses Werkzeug zur ersten Wahl bei Matheaufgaben, in Programmier-Interviews und immer dann, wenn du das n-te Glied willst, ohne die ganze Kette von Hand aufzuschreiben.
Gib eine ganze Zahl von 0 bis 78 ein, um ihre Fibonacci-Zahl sofort zu erhalten.
Eine kurze Regel, von unten nach oben angewendet, ausgehend von den beiden festen Werten F(0) = 0 und F(1) = 1.
F(n) = F(n − 1) + F(n − 2)Der Rechner ruft sich nicht immer wieder selbst auf — das würde dieselbe Arbeit unzählige Male wiederholen. Stattdessen merkt er sich nur zwei laufende Zahlen, startet sie bei 0 und 1 und geht Glied für Glied vor, bis er Position n erreicht. Nach n Schritten hält die erste der beiden Zahlen F(n), sodass die Antwort selbst bei großen Indizes schnell vorliegt.
Angenommen, du möchtest F(10), die Fibonacci-Zahl an Position 10.
Das Paar starten
Beginne mit F(0) = 0 und F(1) = 1 — den beiden festen Startwerten.
Die Folge aufbauen
Addiere jedes Mal die letzten beiden: 1, 2, 3, 5, 8, 13, 21, 34, 55 — das ist F(2) bis F(10).
Die Antwort ablesen
Das Glied an Position 10 ist 55, also F(10) = 55.
Die Zahl, die du zurückbekommst, ist einfach das Glied an Position n der Folge, wobei F(0) = 0 das allererste Glied ist. F(10) = 55 bedeutet also, dass der elfte Wert der Kette (der nullte, erste, zweite … bis zum zehnten) gleich 55 ist. Das Verblüffendste an diesen Zahlen zeigt sich, wenn du jede durch die davor teilst: Die Verhältnisse nähern sich dem goldenen Schnitt φ ≈ 1,618. So ist etwa 55 ÷ 34 ≈ 1,6176 und das nächste Paar 89 ÷ 55 ≈ 1,6182 — je größer der Index, desto enger schmiegt sich das Ergebnis an φ. Genau diese eine Eigenschaft erklärt, warum die Folge so weit verbreitet ist: in den Spiralen von Sonnenblumenköpfen und Tannenzapfen, in der Verzweigung von Bäumen und der Anordnung von Blättern und überall in der Informatik in Algorithmen, Datenstrukturen und Suchverfahren. Die Werte wachsen außerdem schnell — sie vervielfachen sich grob mit 1,618 pro Schritt — weshalb dieses Werkzeug bei F(78) endet: Darüber hinaus passt die exakte ganze Zahl nicht mehr ohne Rundung in eine übliche Computerzahl.
Die Rekursion ist exakt, doch ein paar praktische Punkte solltest du im Blick behalten.
Ganze Indizes und die Genauigkeitsgrenze
Der Index n muss eine ganze Zahl ab 0 sein — an einem Bruch oder einer negativen Position gibt es hier kein Fibonacci-Glied, deshalb liefern diese kein Ergebnis. Der Rechner endet außerdem bei F(78) = 8.944.394.323.791.464, dem letzten Glied, das eine übliche Computerzahl exakt speichern kann. Fragst du einen größeren Index ab, kommt kein Ergebnis zurück statt eines Werts, der still an Genauigkeit verloren hätte.