© Sashkin/Shutterstock.com
Die Fibonacci-Folge ist zweifellos eine der berühmtesten mathematischen Folgen aller Zeiten. Mathematiker und Wissenschaftler verwenden diese Folge seit Jahrhunderten in Mathematik und Naturwissenschaften und haben sie nach dem berühmten italienischen Mathematiker Fibonacci aus dem Mittelalter benannt.
Die Fibonacci-Folge ist eine Reihe von Zahlen, bei denen jede nachfolgende Zahl die Summe der beiden vorhergehenden ist, beginnend bei 0 und 1. Die Folge wird oft mit Fn bezeichnet und sieht folgendermaßen aus: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 und so weiter.
Aber Was ist die große Sache? Warum sollten wir uns um die Fibonacci-Folge kümmern? Nun, es stellt sich heraus, dass diese Folge nicht nur eine beliebige Reihe von Zahlen ist.
Die Fibonacci-Folge findet sich überall in der Natur und in vielen Bereichen der Wissenschaft und hat wichtige Anwendungen in der Informatik und Programmierung. Die Bedeutung der Reihe in der Informatik rührt von den verschiedenen Algorithmen her, die ihre Zahlen erzeugen können.
Programmiersprachen wie Python haben eingebaute Funktionen, um die Fibonacci-Folge zu erzeugen. Wenn Sie daran interessiert sind, die Algorithmen hinter diesen Funktionen zu verstehen, bleiben Sie in der Nähe, da dieser Artikel einige 7 Hauptalgorithmen und Methoden erklärt, die zum Generieren der Fibonacci-Zahlen verwendet werden.
Verschiedene Methoden zum Erstellen von Programmen für Fibonacci-Zahlen
Es gibt mehrere Methoden/Ansätze zur Generierung von Fibonacci-Zahlen, jede mit unterschiedlicher zeitlicher und räumlicher Komplexität. Der einfachste Weg, die n-te Fibonacci-Zahl zu finden, ist die Rekursion.
Dieser Ansatz ist jedoch nicht sehr effizient und kann zu vielen redundanten Berechnungen führen. Wir werden daher die Rekursion zusammen mit anderen Methoden untersuchen, um zu sehen, welche als die effizienteste(n) betrachtet werden kann.
Rekursion
Rekursion ist eine Methode zur Lösung eines Problems, bei der die Lösung hängt von den Lösungen für kleinere Instanzen desselben Problems ab. Im Zusammenhang mit der Fibonacci-Folge funktioniert die rekursive Lösung, indem sie das Problem, die n-te Fibonacci-Zahl zu finden, in zwei kleinere Probleme zerlegt: das Finden der (n-1)-ten Fibonacci-Zahl und das Finden der (n-2)-ten Fibonacci-Zahl.
Dieser Prozess setzt sich rekursiv fort, bis der Basisfall erreicht ist, wobei n entweder 0 oder 1 ist. Der Basisfall stellt die Bedingung dar, die die Funktion erfüllen muss, um sich selbst nicht mehr aufzurufen. Einmal erfüllt, gibt die Funktion einfach n zurück. Für alle anderen Werte von n ruft sich die Funktion rekursiv selbst auf und übergibt n-1 und n-2 als Argumente/Parameter.
Das folgende Beispiel zeigt ein einfaches Python-Programm, das Rekursion implementiert, um Fibonacci-Zahlen zu generieren:
def fibonacci(n):
if n=1: # Basisfall
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # Output: 13
Die Funktion prüft zuerst den Basisfall worauf es n zurückgibt. Wenn n größer als 1 ist, ruft sich die Funktion rekursiv selbst mit n-1 und n-2 als Argumenten auf und addiert ihre Rückgabewerte zusammen. Dies liegt daran, dass die n-te Zahl in einer Fibonacci-Folge gleich der Summe der (n-1)-ten und (n-2)-ten Zahlen in der Folge ist.
Die rekursiven Aufrufe werden fortgesetzt bis der Basisfall erreicht ist und die Funktion die n-te Zahl in der Sequenz zurückgibt. Wir können die Zeitkomplexität der rekursiven Lösung erhalten – sie ist exponentiell O(2n), da die Funktion sich selbst zweimal für jeden Wert von n aufruft.
Dies kann schnell ineffizient werden, wenn n größer wird, wodurch diese Methode für größere Werte von n unpraktisch wird. Die Raumkomplexität ist O(n), was linear ist, da die maximale Tiefe des Rekursionsbaums n ist.
Iteration
Iteration ist ein effizienterer Ansatz zur Lösung der Fibonacci-Folge Problem. Der iterative Ansatz beinhaltet das Lösen eines Problems durch wiederholtes Ausführen einer Reihe von Anweisungen, bis eine bestimmte Bedingung erfüllt ist.
Im Kontext der Fibonacci-Folge funktioniert die iterative Lösung, indem sie mit den ersten beiden Fibonacci-Zahlen beginnt und rechnet die nächste Fibonacci-Zahl unter Verwendung der beiden vorherigen. Dieser Vorgang wird fortgesetzt, bis die n-te Fibonacci-Zahl berechnet ist.
Die Fibonacci-Folge erschien erstmals im lateinischen Manuskript „Liber Abaci“ (1202), wo sie zur Berechnung des Wachstums von Kaninchenpopulationen verwendet wurde.
©TippaPatt/Shutterstock.com
Wir können ein einfaches Programm mit Iteration implementieren, um Fibonacci-Zahlen auf folgende Weise zu erstellen:
def fibonacci(n):
if n==0:
return 0
elif n==1:
return 1
else:
fib1, fib2=0, 1
für i im Bereich (2, n+1):
fib=fib1 + fib2
fib1, fib2=fib2, fib
return fib2
Hier verwenden wir eine Schleife, um die n-te Fibonacci-Zahl in linearer Zeit zu berechnen. Wir erreichen dies, indem wir mit den ersten beiden Zahlen in der Folge (0 und 1) beginnen und die nächste Zahl iterativ als Summe der beiden vorherigen berechnen.
Wir verfolgen die vorherigen zwei Zahlen in Variablen und aktualisieren sie bei jeder Iteration. Nach n Iterationen geben wir die n-te Zahl zurück.
Die zeitliche Komplexität der iterativen Lösung ist O(n), was linear ist. Dies liegt daran, dass die for-Schleife n-1 Mal ausgeführt wird, um die n-te Fibonacci-Zahl zu berechnen. Da die Funktion nur eine konstante Anzahl von Variablen verwendet, um die n-te Fibonacci-Zahl zu berechnen, ist ihre Raumkomplexität O(1), was konstant ist.
Memoisierung
Memoisierung ist eine Methode von Lösen eines Problems durch Speichern der Ergebnisse teurer Funktionsaufrufe und Zurückgeben des zwischengespeicherten Ergebnisses, wenn dieselben Eingaben erneut erfolgen.
Im Kontext der Fibonacci-Folge funktioniert die Memoisierungslösung, indem sie die Lösungen von Teilproblemen speichert und das zwischengespeicherte Ergebnis zurückgibt, falls verfügbar.
Auf diese Weise berechnet das Programm die Lösung zu jedem Unterproblem nur einmal und verwendet es bei Bedarf wieder.
Hier ist ein Beispiel für die Implementierung von Memoisierung:
def fibonacci(n, memo={}):
if n in memo:
memo zurückgeben[n]
elif n=1:
n zurückgeben
else:
memo[n]=fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
In diesem Beispiel wird ein Top verwendet-down-Ansatz zur Berechnung der n-ten Fibonacci-Zahl durch Zwischenspeichern zuvor berechneter Werte, um redundante Berechnungen zu vermeiden. Die Funktion prüft zunächst, ob sie den Wert der n-ten Fibonacci-Zahl bereits berechnet und in einem Python-Wörterbuch zwischengespeichert hat. Wenn dies der Fall ist, wird der zwischengespeicherte Wert zurückgegeben.
Ist dies nicht der Fall, berechnet es den Wert rekursiv als Summe der (n-1)-ten und (n-2)-ten Fibonacci-Zahlen, speichert den berechneten Wert im Wörterbuch und zwischen gibt es zurück.
Die zeitliche Komplexität der Memoisierungslösung ist O(n), was linear ist. Dies liegt daran, dass das Programm jede Fibonacci-Zahl nur einmal berechnet und sie zur späteren Verwendung im Memo-Wörterbuch speichert. Die Raumkomplexität ist ebenfalls O(n), was linear ist, da das Memo-Wörterbuch Lösungen für Teilprobleme bis zu n speichert.
Dynamische Programmierung
Dynamische Programmierung ist eine Methode zur Lösung von a Problem, indem Sie es in kleinere Teilprobleme zerlegen und die Lösungen dieser Teilprobleme speichern, um redundante Berechnungen zu vermeiden.
Im Kontext der Fibonacci-Folge funktioniert die dynamische Programmierlösung, indem sie die Fibonacci-Zahlen von unten nach oben berechnet und die Lösungen in einem Array speichert. Auf diese Weise wird die Lösung für jedes Teilproblem nur einmal berechnet und bei Bedarf wiederverwendet.
Betrachten Sie das folgende Beispiel:
def fibonacci(n):
fib=[0, 1]
für i im Bereich (2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
Die Funktion verwendet eine Python-Liste, um die berechneten Werte der Sequenz zu speichern, beginnend mit den ersten beiden Werten. Dann iteriert es von 2 bis n, berechnet den i-ten Wert als die Summe der (i-1)-ten und (i-2)-ten Werte und speichert ihn in der Liste. Schließlich gibt es den n-ten Wert in der Liste zurück.
Die Zeitkomplexität der dynamischen Programmierlösung ist O(n), was linear ist. Die Zeitkomplexität des Algorithmus ist O(n), da die for-Schleife die n-te Fibonacci-Zahl berechnet, indem sie n-1 Mal ausgeführt wird, und jede Berechnung eine konstante Zeit in Anspruch nimmt.
Darüber hinaus ist die Platzkomplexität des Algorithmus O(n), da er eine Liste der Größe n verwendet, um die Lösungen von Teilproblemen zu speichern.
Matrixexponentiation
Matrixpotenzierung ist eine Methode zur Lösung eines Problems durch Potenzieren einer Matrix. Im Zusammenhang mit der Fibonacci-Folge funktioniert die Matrixexponentiationslösung, indem sie eine Matrix mit Fibonacci-Zahlen verwendet, um sie mit n-1 zu potenzieren, um die n-te Fibonacci-Zahl zu erhalten.
Sie können die Matrixexponentiation dazu verwenden Erstellen Sie ein Python-Programm für Fibonacci-Zahlen wie gezeigt:
import numpy as np
def fibonacci(n):
F=np.array([[ 1, 1], [1, 0]])
return np.linalg.matrix_power(F, n-1)[0, 0]
In diesem Beispiel haben wir’Verwenden Sie eine Matrix-Potenzierungstechnik, um die n-te Fibonacci-Zahl in logarithmischer Zeit zu berechnen. Dazu potenzieren wir eine 2×2-Matrix mit n-1 und multiplizieren sie mit dem Anfangszustandsvektor [0, 1]. Die resultierende Matrix enthält die n-te und (n+1)-te Fibonacci-Zahl, und wir geben die n-te Zahl zurück.
Die Zeitkomplexität der Matrixexponentiationslösung ist O(log n), was natürlich logarithmisch ist. Der bei der Matrixmultiplikation verwendete Teile-und-Herrsche-Algorithmus verringert die Anzahl der erforderlichen Multiplikationen. Daher ist die Raumkomplexität O(1), was konstant ist, da nur eine konstante Menge an Speicher verwendet wird.
Binet-Formel
Die Binet-Formel ist eine direkte Formel zur Berechnung der n-te Fibonacci-Zahl, ohne alle vorherigen Fibonacci-Zahlen berechnen zu müssen.
Die Formel wird oft geschrieben als: Fn=round((Φ^n – (1-Φ)^n)/√5), wobei Φ (phi) der goldene Schnitt ist.
Binets Formel legt dies nahe das Verhältnis zweier aufeinanderfolgender Fibonacci-Zahlen tendiert zum Goldenen Schnitt, wenn n zunimmt.
©TippaPatt/Shutterstock.com
Im Zusammenhang mit der Fibonacci-Folge funktioniert Binets Formel unter Verwendung des Goldenen Schnitts, der ist (1 + √5)/2, und seine Konjugierte, die 1 – √5)/2 ist.
Ein Beispiel in Python wäre:
def fibonacci(n):
goldenes_Verhältnis=(1 + 5**0,5)/2
Rückrunde ((goldenes_Verhältnis**n – (1 – goldenes_Verhältnis)**n)/5**0,5 )
Die Funktion definiert zunächst den Goldenen Schnitt. Als nächstes berechnen wir den n-ten Term mit der Formel von Binet und geben den gerundeten ganzzahligen Wert des Ergebnisses zurück.
Diese Implementierung der Binet-Formel ist rechnerisch effizient, da nur wenige einfache arithmetische Operationen erforderlich sind, um einen beliebigen Term der Fibonacci-Folge zu berechnen, ohne dass alle vorhergehenden Terme berechnet werden müssen.
Dies wird durch die Zeitkomplexität von Binets Formel von O(1) bewiesen, die konstant ist. Denn die Formel benötigt nur wenige Rechenoperationen, um die n-te Fibonacci-Zahl zu berechnen. Die Raumkomplexität ist O(1), was konstant ist, weil das Programm nur wenige Variablen verwendet, um die n-te Fibonacci-Zahl zu berechnen.
Greedy-Algorithmus
Der Greedy-Algorithmus ist eine Technik verwendet, um Optimierungsprobleme zu lösen. Es funktioniert, indem es bei jedem Schritt die beste Entscheidung trifft und hofft, dass die getroffenen Entscheidungen zu einer optimalen Lösung führen. Dieser Algorithmus folgt der „gierigen“ Strategie, bei jedem Schritt immer die größtmögliche Zahl zu wählen.
Man kann mit diesem Ansatz Fibonacci-Zahlen generieren, indem man mit den beiden Basisfällen beginnt und dann durch die Reihe iteriert, um die zu finden nächste Zahl.
Speichern Sie zuerst die beiden vorhergehenden Zahlen in zwei Variablen und addieren Sie sie dann, um die nächste Fibonacci-Zahl zu erhalten. Dieser Prozess setzt sich fort, bis die n-te Zahl in der Folge generiert ist.
Wir können ein Programm für Fibonacci-Zahlen mit dem Greedy-Algorithmus auf einfache Weise wie folgt implementieren:
def fibonacci(n):
if n=1:
return n
prev, curr=0, 1
for i in range(2, n+1):
prev, curr=curr, prev + curr
return curr
Wir prüfen zuerst, ob n den Basisfall erfüllt , in diesem Fall haben wir den entsprechenden Wert zurückgegeben. Andernfalls erstellen wir eine Liste, um die beiden vorherigen Fibonacci-Zahlen (0 und 1) zu speichern, und verwenden dann eine Schleife, um die nächsten Zahlen in der Sequenz zu generieren, indem wir die letzten beiden Zahlen in der Liste hinzufügen. Die Schleife wird fortgesetzt, bis die n-te Zahl in der Folge generiert wird, an welchem Punkt wir sie zurückgeben.
Die Zeitkomplexität des Greedy-Algorithmus ist O(n), was linear ist, wie wir es brauchen n-mal iterieren, um die n-te Zahl in der Folge zu erzeugen. Die Raumkomplexität ist auch O(n), da wir die vorherigen zwei Zahlen in der Sequenz für jede Iteration der Schleife speichern müssen.
Allerdings könnten wir die Raumkomplexität optimieren, indem wir nur die vorherigen zwei Zahlen speichern, anstatt alle bisher generierten Zahlen.
Aufrundung
Die Fibonacci-Folge ist ein wichtiges und zeitloses mathematisches Konzept mit zahlreichen Anwendungen in der Informatik und Programmierung. Mit dem richtigen Algorithmus können Sie schnell und einfach jede Fibonacci-Zahl generieren.
Im Allgemeinen sind Iteration und dynamische Programmierung die effizientesten Algorithmen in Bezug auf Zeit-und Raumkomplexität, während Matrixexponentiation in Bezug auf Zeitkomplexität für größere Werte von n am effizientesten ist. Rekursion ist am intuitivsten, aber auch am wenigsten effizient in Bezug auf Zeit-und Raumkomplexität.
Letztendlich hängt der beste Algorithmus vom jeweiligen Problem ab. Daher ist es wichtig, sie zu verstehen, um zu wissen, wann Sie welche Methoden zur Optimierung der Leistung Ihrer Fibonacci-Programme anwenden sollten.
Programm für Fibonacci-Zahlen mit Beispielen, häufig gestellte Fragen (FAQs)
Archimedes-Spirale, Goldener Schnitt, Fibonacci-Folge: Was ist die Verbindung?
Die Archimedes-Spirale und die Fibonacci-Folge können durch den Goldenen Schnitt in Beziehung gesetzt werden.
Die Der Goldene Schnitt ist eine mathematische Konstante, die dem Verhältnis zweier Zahlen in der Fibonacci-Folge entspricht. Dieses Verhältnis kann auch in Form der Archimedischen Spirale gefunden werden.
Daher sind die drei Konzepte miteinander verbunden und haben wichtige Anwendungen in Mathematik, Wissenschaft und Kunst.
Was ist der Unterschied zwischen Rekursion und Iteration beim Generieren von Fibonacci-Zahlen?
Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, während Iteration eine Schleifenstruktur ist, die eine Reihe von wiederholt Anweisungen, bis eine bestimmte Bedingung erfüllt ist.
Rekursion ist der einfachste Ansatz zur Generierung von Fibonacci-Zahlen, aber aufgrund ihrer exponentiellen Zeitkomplexität ineffizient. Iteration ist effizienter und kann die n-te Zahl in linearer Zeit berechnen.
Wie wird die Fibonacci-Folge auf Informatik und Programmierung angewendet?
Die Die Fibonacci-Folge hat viele Anwendungen, z. B. in Algorithmen zum Generieren von Zufallszahlen, Diagrammen, Bäumen, Sortieralgorithmen und Datenkomprimierung. Darüber hinaus wird die Fibonacci-Folge in der Kryptografie und bei der Analyse der Leistung von Algorithmen verwendet.
Welche Bedeutung hat die Fibonacci-Folge?
Sie ist es oft Wird verwendet, um Wachstumsmuster in der Natur zu modellieren, wie z. B. die Verzweigung von Bäumen, die Anordnung von Blättern an einem Stamm und die Spiralen in einer Muschel oder einem Tannenzapfen. Es wird auch in der technischen Analyse verwendet, um Markttrends vorherzusagen, und in der Kryptografie, um Zufallszahlen zu generieren.
Was sind einige Beispiele für Fibonacci-Zahlen in Natur und Kunst?
Der Goldene Schnitt findet sich in vielen Naturphänomenen wie den Spiralen in bestimmten Pflanzen und Tieren (z. B. Ananas, Sonnenblumen, Muscheln usw.).
Er findet sich auch in bestimmten Strukturen wie dem Parthenon in Athen, Griechenland, Musik wie Beethovens Fünfte Symphonie, Kunst wie Leonardo da Vincis Mona Lisa und Astronomie wie die Umlaufbahnen von Planeten um Sterne.