Fibonacci-Zahlen in der Python-Sprache

Fibonacci-Zahlen sind eine bestimmte Folge, bei der der erste Wert als 0 vordeklariert ist und der zweite Wert als 1 vordeklariert ist. Der Rest der Zahlen wird aus diesen beiden erzeugt, indem die beiden vorherigen Zahlen addiert werden. Alle Fibonacci-Zahlen sind positive ganze Zahlen, beginnend bei 0. Die ersten zwölf Fibonacci-Zahlen und wie sie erhalten werden, lauten wie folgt:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

Ohne die Summenausdrücke können diese Fibonacci-Zahlen wie folgt in eine Tabelle eingetragen werden:

Die erste Reihe enthält die Fibonacci-Zahlen. Die zweite Zeile hat nullbasierte Indizes, vorausgesetzt, die Fibonacci-Zahlen befinden sich in einem Array.

Fibonacci-Zahlen können in O(n)-Zeit und in O(1)-Zeit erzeugt werden. In diesen Zeitkomplexitätsausdrücken bedeutet n n Hauptoperationen und 1 bedeutet 1 Hauptoperation. Bei O(n) werden n Fibonacci-Zahlen erzeugt, beginnend bei 0. Bei O(1) wird eine Fibonacci-Zahl aus einem entsprechenden Index erzeugt. Deshalb braucht es statt n Hauptoperationen nur eine Hauptoperation.

Das Ziel dieses Artikels ist es, zu erklären, wie man Fibonacci-Zahlen mit Python erzeugt.

Formel für eine Fibonacci-Zahl

Die formale Definition einer Fibonacci-Zahl lautet:

wo f _n ist die Fibonacci-Zahl beim nullbasierten n

Produzieren von Fibonacci-Zahlen in O(n)-Zeit

Wenn n 1 ist, dann würde nur 0 als Fibonacci-Zahl gedruckt werden. Wenn n 2 ist, werden 0 und 1 als Fibonacci-Zahlen in dieser Reihenfolge gedruckt. Wenn n 3 ist, werden 0, 1 und 1 in dieser Reihenfolge als Fibonacci-Zahlen gedruckt. Wenn n 4 ist, werden 0, 1, 1 und 2 in dieser Reihenfolge als Fibonacci-Zahlen gedruckt. Wenn n 5 ist, werden 0, 1, 1, 2 und 3 in dieser Reihenfolge als Fibonacci-Zahlen gedruckt. Wenn n 6 ist, dann würden 0, 1, 1, 2, 3 und 5 als Fibonacci-Zahlen gedruckt werden, in dieser Reihenfolge – und so weiter.

Die Python-Funktion zum Erzeugen der ersten n Fibonacci-Zahlen lautet:

Es beginnt mit der Erstellung eines Arrays aus n Elementen, die alle mit Nullen initialisiert sind. Dieses Array enthält die Fibonacci-Zahlen. Die erste Fibonacci-Zahl, 0, ist bereits da. Die zweite Fibonacci-Zahl, 1, wird durch die nächste Anweisung (in der Funktion) zugewiesen. Dann gibt es noch die for-Schleife, die von Index 2 bis kurz vor n beginnt. Es hat die Aussage:

Dies addiert die unmittelbar vorhergehenden zwei Zahlen.

Code zum Aufrufen der Funktion und zum Drucken der ersten zwölf Fibonacci-Zahlen kann sein:

N = 12
A = Fibonacci(N)
für i im Bereich (N):
print (A[i], end=’ ‘)
drucken()

Die Ausgabe ist:

Produzieren einer Fibonacci-Zahl in konstanter Zeit

Es gibt eine mathematische Formel, die einen nullbasierten Index mit seiner entsprechenden Fibonacci-Zahl in Beziehung setzt. Die Formel lautet:

Beachten Sie, dass auf der rechten Seite der Gleichung nicht die Quadratwurzel von 5 mit n potenziert wird; es ist der Ausdruck in Klammern, der mit n potenziert wird. Es gibt zwei solcher Ausdrücke.

Wenn n 0 ist, wäre Fibn 0. Wenn n 1 ist, wäre Fib _n wäre 1. Wenn n 2 ist, Fib _n wäre 1. Wenn n 3 ist, Fib _n wäre 2. Wenn n 4 ist, Fib _n wäre 3 – und so weiter. Der Leser kann diese Formel mathematisch verifizieren, indem er verschiedene Werte für n einsetzt und auswertet. n ist in dieser Formel ein nullbasierter Index.

Der Python-Code für diese Formel lautet:

Mathematik importieren

Das Mathematikmodul wurde importiert. Es hat die Quadratwurzelfunktion. Der Operator ** wird für die Leistung verwendet. Die Funktion fibNo() implementiert die Formel direkt. Ein geeigneter Aufruf und Ausdruck für die Funktion fibNo() ist:

N = 11
rechts = fibNo(N)
drucken (ret)

Die Ausgabe ist:

Es ist möglich, die unnötigen Dezimalstellen aus der Antwort zu entfernen. Aber das ist eine Diskussion für ein andermal.

Wenn für verschiedene n Indizes unterschiedliche Fibonacci-Zahlen benötigt werden, muss die Funktion fibNo() für jeden der n Indizes einmal aufgerufen werden, um die unterschiedlichen entsprechenden Fibonacci-Zahlen zurückzugeben. Das folgende Programm tut dies für die nullbasierten Indizes 7 bis 9 (einschließlich) :

Mathematik importieren

Die Ausgabe ist:

Beachten Sie, wie die for-Schleife in Python codiert wurde. Der erste Index ist 7. Der nächste Index ist 8 und der letzte Index ist 9. 10 im Range-Argument ist 9 + 1. Der Wert an der Position 10 muss der letzte nullbasierte Index plus 1 sein. Der erste Argument 7 ist der nullbasierte Startindex.

Fazit

Fibonacci-Zahlen sind eine bestimmte Folge ganzer Zahlen (positive ganze Zahlen). Es beginnt mit 0, gefolgt von 1 bedingungslos. Der Rest der Zahlen wird von dort aus entwickelt, indem die unmittelbar vorhergehenden zwei Zahlen addiert werden.

Um die ersten n Fibonacci-Zahlen zu erhalten, akzeptieren Sie 0 und 1 als die ersten beiden und verwenden Sie dann für den Rest eine for-Schleife mit einer Anweisung wie:

die die unmittelbar vorhergehenden zwei Zahlen addiert.

Um nur eine Fibonacci-Zahl aus einem nullbasierten Index n zu erhalten, verwenden Sie die Formel: