Fibonacci Generator

Die Fibonacci-Folge ist eine Reihe, bei der jede Zahl die Summe der beiden vorhergehenden ist: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... Benannt nach Leonardo von Pisa (Fibonacci), der sie 1202 durch sein Buch Liber Abaci in die europäische Mathematik einführte. Die Folge taucht in der Natur auf: in der spiralförmigen Anordnung von Sonnenblumensamen, Tannenzapfenschuppen, Blattphyllotaxis, Nautilasschalen und in der Verzweigung von Bäumen.

Der goldene Schnitt (φ ≈ 1,6180339887...) ist der Grenzwert von F(n+1)/F(n) für n → ∞. Der genaue Wert ist (1 + √5) / 2. Zwei Größen stehen im goldenen Schnitt, wenn ihr Verhältnis dasselbe ist wie das Verhältnis ihrer Summe zur größeren Größe: (a+b)/a = a/b = φ. Der goldene Schnitt erscheint in der euklidischen Geometrie, Kunst, Architektur (Parthenon) und hat Mathematiker seit Langem fasziniert. Er ist auch mit dem regulären Fünfeck und dem Ikosaeder verwandt.

Die Anzahl der Spiralen in Sonnenblumen, Tannenzapfen und Ananas sind aufeinanderfolgende Fibonacci-Zahlen (typischerweise 21 und 34 oder 34 und 55). Die Anzahl der Blütenblätter vieler Blumen ist eine Fibonacci-Zahl (3, 5, 8, 13). Blattanordnungen an Stielen folgen Fibonacci-Brüchen, um die Sonnenexposition zu maximieren. Das Kaninchenpopulationsmodell, mit dem Fibonacci die Folge einführte: Wenn ein Kaninchenpaar ab dem zweiten Monat jeden Monat ein neues Paar produziert, wächst die Population entsprechend der Fibonacci-Folge.

Naive Rekursion: O(2^n) – exponentielle Zeit. Memoized Rekursion oder Iteration: O(n). Matrixexponentiation: O(log n). Geschlossene Binet-Formel: F(n) = (φ^n − ψ^n) / √5, wobei ψ = (1−√5)/2 – theoretisch O(1), verliert aber bei großem n aufgrund von Gleitkommafehlern an Genauigkeit. Für genaue große Fibonacci-Zahlen verwenden Sie beliebig genaue Integer-Arithmetik (Pythons int, Javas BigInteger). F(100) hat 21 Ziffern; F(1000) hat 209 Ziffern.

Fibonacci-Heaps (verwendet in Dijkstras Algorithmus), Fibonacci-Suche (Alternative zur Binärsuche), Pseudozufallszahlengeneratoren, Zeckendorf-Theorem (jede positive ganze Zahl ist eindeutig als Summe nicht aufeinanderfolgender Fibonacci-Zahlen darstellbar), Fibonacci-Kodierung (universeller Code für Integer-Kompression), Skip-List-Zufallsebenen-Generierung und Analyse von Worst-Case-Eingaben für bestimmte Algorithmen wie Euklids GCD-Algorithmus.