Python-Programm zum Drucken der Fibonacci-Folge (2023)

Fragen zur Fibonacci-Reihe gehören zu den am häufigsten gestellten Fragen in Python-Interviews.

In diesem Artikel erkläre ich Schritt für Schritt, wie man die Fibonacci-Folge mit zwei verschiedenen Techniken ausdruckt: Iteration und Rekursion.

Bevor wir beginnen, wollen wir zunächst einige grundlegende Begriffe verstehen.

Was ist die Fibonacci-Folge?

DerFibonacci-Folgeist eine Zahlenfolge, bei der eine gegebene Zahl das Ergebnis der Addition der beiden davor stehenden Zahlen ist. Und wenn man die beiden vorherigen Zahlen einige Male addiert, entsteht eine Reihe, die wir die Fibonacci-Reihe nennen.

Die Fibonacci-Folge beginnt mit zwei Zahlen, also 0 und 1. Dann setzt sich jede folgende Zahl aus der Addition der beiden vorherigen Zahlen zusammen.

Nehmen Sie zum Beispiel 0 und 1. Das sind die ersten beiden Zahlen in der Folge. Wenn man sie addiert, erhält man 1. Die Sequenz beginnt also mit 0, 1, 1,...

Um dann die nächste Zahl zu finden, addieren Sie die letzte Zahl, die Sie haben, und die Zahl davor. Also 1+1 = 2. Die Reihenfolge ist also bisher 0, 1, 1, 2, ... Macht das Sinn?

Wir können dies mathematischer darstellen als 0, 1, (1) – [0 + 1]. Ebenso ist die nächste Fibonacci-Zahl - 0, 1, 1, (2) - [1 + 1]. Usw. Hier ist ein Diagramm, das die ersten 10 Fibonacci-Zahlen zeigt:

Dies ist ein Beispiel für eine Fibonacci-Reihe –0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Innerhalb dieser kontinuierlichen Folge ist jede einzelne Zahl eine Fibonacci-Zahl.

Mathematisch wird die Fibonacci-Folge durch diese Formel dargestellt:

F(n) = F(n-1) + F(n-2), Won > 1.

Mit dieser Folge können wir jede n-te Fibonacci-Zahl finden.

Diese faszinierende Sequenz wird häufig mit dem Mathematiker Leonardo Pisano, auch bekannt als Fibonacci, in Verbindung gebracht. Er stammte aus der Republik Pisa und wird daher auch Leonardo von Pisa genannt.

Leonardo galt als einer der talentiertesten Mathematiker des Mittelalters.

So drucken Sie die Fibonacci-Folge in Python

Sie können ein Computerprogramm zum Drucken der Fibonacci-Folge auf zwei verschiedene Arten schreiben:

• Iterativ und
• Rekursiv.

Unter Iteration versteht man die Wiederholung der Arbeit, bis die vorgegebene Bedingung erfüllt ist. Rekursion hingegen bedeutet, eine einzelne Aufgabe auszuführen und mit der nächsten fortzufahren, um die verbleibende Aufgabe auszuführen.

Hier ist ein iterativer Algorithmus zum Drucken der Fibonacci-Folge:

1. Erstellen Sie 2 Variablen und initialisieren Sie sie mit 0 und 1 (erste = 0, zweite = 1)
2. Erstellen Sie eine weitere Variable, um die Länge der zu druckenden Fibonacci-Folge (Länge) zu verfolgen.
3. Schleife (Länge ist kleiner als die Serienlänge)
4. Druckenerster + zweiter
5. AktualisierenErsteUndzweiteVariable (erste zeigt auf die zweite und die zweite zeigt auf erste + zweite)
6. Dekrementieren Sie die Längenvariable und wiederholen Sie den Vorgang ab Schritt 3
7. Sobald die Schleife beendet ist, beenden Sie das Programm

So funktioniert der iterative Algorithmus:

Bedenken Sie, dass wir eine Fibonacci-Folge der Länge 7 drucken müssen. Dann sieht der Ablauf des Algorithmus wie folgt aus:

Die endgültige Fibonacci-Folge für die Länge 7 lautet also[0, 1, 1, 2, 3, 5, 8].

Iterativer Python-Code zum Drucken der Fibonacci-Folge:

def PrintFibonacci(length): #Anfangsvariable für den Basisfall. erste = 0 zweite = 1 #Drucken der anfänglichen Fibonacci-Zahl. print(first, second, end=" ") #Verringerung der Länge um zwei, da die ersten beiden Fibonacci-Zahlen #bereits gedruckt wurden. length -= 2 #Schleife, bis die Länge 0 wird. while length > 0: #Drucken der nächsten Fibonacci-Zahl. print(first + second, end=" ") #Aktualisieren der ersten und zweiten Variablen, um die nächste Zahl zu finden. temp = zweite Sekunde = erste + zweite erste = temp #Verringerung der Länge, die die Fibonacci-Zahlen angibt, die mehr gedruckt werden sollen. length -= 1if __name__ == "__main__": print("Fibonacci Series - ") PrintFibonacci(7) pass

Ausgangfür Länge 7:

Fibonacci-Reihe - 1 1 2 3 5 8

Erläuterung des Kodex:

Im obigen Code haben wir zunächst eine Funktion definiert, die die Fibonacci-Reihe ausgibt. Es akzeptiert einen Parameter für die Länge und die Funktion muss die Fibonacci-Reihe drucken.

Als nächstes haben wir zwei Variablen erstellt, die die ersten beiden Fibonacci-Werte enthalten, also 0 und 1.

Dann haben wir die ersten beiden Werte [0, 1] gedruckt und die Länge um 2 dekrementiert, da bereits zwei Werte gedruckt wurden.

Wir führen für die verbleibende Länge eine Schleife aus und drucken jedes Mal den nächsten Fibonacci-Wert aus, indem wir die beiden vorherigen Terme hinzufügen, die in der ersten und zweiten Variablen gespeichert sind (die wir ursprünglich erstellt haben, um die beiden vorherigen Werte im Auge zu behalten).

Aktualisieren Sie den ersten und zweiten Wert, der auf die beiden vorherigen Werte verweist [erster = zweiter und zweiter = vorheriger erster + zweiter].

Die Schleife wird ausgeführt, bis die Länge 0 wird, was bedeutet, dass die erforderliche Länge der Fibonacci-Folge gedruckt wird.

Dann rufen wir die zum Drucken von Fibonacci definierte Funktion aus der Hauptfunktion auf, indem wir das Argument der erforderlichen zu druckenden Länge übergeben. Und da haben Sie es!

Es gibt einen anderen Ansatz zum Drucken der Fibonacci-Folge mithilfe der Rekursion. Lassen Sie uns also auch diesen Ansatz verstehen.

Rekursiver Algorithmus zum Drucken der Fibonacci-Folge:

• Übernehmen Sie den Wert der vorherigen ersten und zweiten Fibonacci-Zahl als zu druckende Länge.
• Überprüfen Sie, ob die Länge 0 ist, und beenden Sie dann den Funktionsaufruf.
• Drucken Sie den Fibonacci-Wert aus, indem Sie die beiden vorherigen Werte addieren, die im Parameter der Funktion empfangen wurden (erster und zweiter).
• Rufen Sie die Funktion rekursiv für den aktualisierten Wert des ersten und zweiten Wertes sowie den verringerten Längenwert auf.

Für diesen rekursiven Funktionsaufruf müssen wir den Anfangswert von Fibonacci, also (0 und 1), in der ersten und zweiten Variablen übergeben.

Damit Sie diesen Algorithmus besser verstehen, sehen wir uns die Python-Implementierung der Algorithmen an. Dann schauen wir uns ein Beispiel an, damit Sie sehen können, wie dieser rekursive Algorithmus funktioniert.

Rekursiver Python-Code zum Drucken der Fibonacci-Folge:

def PrintFibonacci(first, second, length): #Stoppt das Drucken und den rekursiven Aufruf, wenn die Länge das #Ende erreicht. if(length == 0): return #Printng die nächste Fibonacci-Zahl. print(first + second, end=" ") #Rekursiver Aufruf der Funktion durch Aktualisieren des Werts und #Dekrementieren der Länge. PrintFibonacci(second, first+second, length-1)if __name__ == "__main__": #Anfängliche 2 Werte drucken. print(0,1,end=" ") #Aufrufen der Funktion zum Drucken der verbleibenden Länge #Fibonacci-Reihe PrintFibonacci(0,1,7-2)

Ausgang:

Für Länge 7 1 1 2 3 5 8Für Länge 101 1 2 3 5 8 13 21 34

Erklärung des Codes:

Zuerst haben wir eine Funktion erstellt und eine Rekursion darauf durchgeführt. In dieser Funktion haben wir den Wert der beiden vorherigen Fibonacci-Zahlen akzeptiert, um die aktuelle Fibonacci-Zahl zu berechnen. Und wir haben eine Länge, die den Überblick über den Basisfall behält.

Für den Basisfall der Rekursion prüfen wir, ob die Länge 0 erreicht. Wenn dies der Fall ist, beenden wir den rekursiven Aufruf.

In anderen Fällen drucken wir die Fibonacci-Zahl aus, indem wir die beiden vorherigen Fibonacci-Zahlen addieren.

Und dann rufen wir die Funktion rekursiv auf, um den nächsten Fibonacci-Wert auszugeben, indem wir die beiden vorherigen Werte aktualisieren und die Länge dekrementieren.

Lassen Sie uns nun die rekursiven Aufrufe dieser Funktion mithilfe eines Rekursionsbaums visualisieren. Die Länge, die gedruckt werden soll, beträgt 7.

Bevor der rekursive Aufruf erfolgt, gibt die Hauptfunktion die beiden Anfangswerte 0 und 1 aus. Anschließend übergibt sie diese Werte an die rekursive Funktion.

Die rekursive Funktion gibt den Wert (0 + 1) aus und ruft rekursiv mit dem nächsten aktualisierten Wert auf.

Dann gibt die rekursive Funktion den Wert aus(1 + 1)und ruft rekursiv mit dem nächsten aktualisierten Wert auf.

Jetzt gibt die rekursive Funktion den Wert aus(1 + 2)und ruft rekursiv mit dem nächsten aktualisierten Wert auf.

Und dann gibt die rekursive Funktion den Wert aus(2 + 3)und ruft rekursiv mit dem nächsten aktualisierten Wert auf.

Jetzt gibt die rekursive Funktion den Wert aus(3 + 5)und ruft rekursiv mit dem nächsten aktualisierten Wert auf.

Schließlich erfolgt der letzte Anruf. Und die Länge ist 0, sodass der rekursive Aufruf erneut beendet wird und die Serie auf der Konsole gedruckt wird.

Zeitkomplexitätsanalyse

Für den iterativen Ansatz

Im iterativen Algorithmus durchlaufen wir eine Schleife, bis die Länge 0 wird. In der Schleife führen wir eine konstante Zeitoperation aus, bei der der Wert gedruckt und die Variablen aktualisiert werden.

Wenn wir davon ausgehen, dass diese Länge n ist, dann beträgt die ZeitkomplexitätAn).

Für den rekursiven Ansatz

Beim rekursiven Ansatz rufen wir rekursive Funktionen bis zur angegebenen Länge so oft auf. Wir führen auch einen einfachen, ständigen Druckvorgang durch.

Wenn wir also davon ausgehen, dass es sich bei der Länge um n Zahlen handelt, beträgt die zeitliche KomplexitätAn).

Raumkomplexitätsanalyse

Für iterativen Ansatz

Beim iterativen Ansatz haben wir nicht den zusätzlichen Speicher genutzt, um die beiden Variablen zu akzeptieren, die die beiden vorherigen Fibonacci-Zahlen und die Konstante für eine beliebige Zahl der Reihenlänge verfolgen. Die Raumkomplexität wird also konstant O(1) sein.

Für den rekursiven Ansatz

Beim rekursiven Ansatz rufen wir die Längenfunktionen mehrmals auf. Wir wissen, dass die Rekursion intern einen Aufrufstapel verwendet.

Wenn wir davon ausgehen, dass es sich dabei um den vom Programm beanspruchten Speicher handelt, wird der rekursive Aufruf so oft ausgeführt, wie die Länge lautet. Dann beträgt die Raumkomplexität O(n).

Abschluss

Die Fibonacci-Folge ist die Zahlenreihe, in der jede Zahl die Addition ihrer beiden vorherigen Zahlen ist.

Fibonacci-Folgen finden sich nicht nur in der Mathematik, sondern überall in der Natur – etwa in Blütenblättern, Blättern oder Stacheln eines Kaktus und so weiter.

Es handelt sich außerdem um eine häufig gestellte Frage in Vorstellungsgesprächen – daher ist es gut zu wissen, wie sie funktioniert.

Ich habe mich von diesem Beitrag inspirieren lassenInterviewBit.