Direkt zum Inhalt

Fibonacci-Sequenz in Python: Kodierungstechniken lernen und erforschen

Entdecke, wie die Fibonacci-Folge funktioniert. Erforsche seine mathematischen Eigenschaften und realen Anwendungen.
Aktualisierte 17. Jan. 2025  · 6 Min. Lesezeit

Die Fibonacci-Folge ist eine lustige Art, Python weiter zu üben. In diesem Artikel erfährst du, wie du die Fibonacci-Folge in Python mit verschiedenen Python-Techniken implementieren kannst: vom Schreiben effizienter Funktionen über den Umgang mit Rekursionen bis hin zur Nutzung objektorientierter Prinzipien für optimierte Lösungen. 

Wenn du ganz durch bist, kannst du unseren Kurs Funktionen schreiben in Python besuchen, um Konzepte wie Scoping und Fehlerbehandlung zu vertiefen, oder unseren Kurs Objektorientierte Programmierung in Python für Fortgeschrittene, um etwas über Vererbung und Basisklassen zu lernen. Jetzt wollen wir die Fibonacci-Folge ausprobieren.

Was ist die Fibonacci-Folge?

Die Fibonacci-Folge ist ein mathematisches Konzept, das in vielen Bereichen der Wissenschaft und Natur vorkommt. Es ist eine Zahlenreihe, bei der jede Zahl die Summe der beiden vorhergehenden ist, beginnend mit 0 und 1. Dieses Muster bildet die Grundlage für Anwendungen in Bereichen wie Informatik und Finanzen. 

Zwei Hauptaspekte machen die Fibonacci-Folge aus: die rekursive Struktur der Folge und ihre Beziehung zum Goldenen Schnitt.

Die rekursive Natur der Fibonacci-Folge

Die Fibonacci-Folge beginnt mit 0 und 1. Jede neue Zahl ist die Summe der beiden Zahlen vor ihr. Zum Beispiel:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

Und so weiter. 

Mathematisch gesehen, schreiben wir es als F(n) = F(n-1) + F(n-2). Die Folge baut sich selbst auf, indem die letzten beiden Zahlen wiederholt addiert werden. Die ersten beiden Zahlen, 0 und 1, sind der Ausgangspunkt oder die Basisfälle. Ohne diese würde die Sequenz nicht funktionieren.

Dieses rekursive Muster dient als Grundlage für einige Algorithmen in der Informatik. Die Rekursion in der Programmierung arbeitet zum Beispiel mit dieser Sequenz, wenn es darum geht, Probleme wie das Generieren von Fibonacci-Zahlen oder das Aufteilen von Aufgaben in kleinere, überschaubare Teile zu lösen.

Verbindung zum Goldenen Schnitt 

Die Fibonacci-Folge ist eng mit dem Goldenen Schnitt verbunden, einer irrationalen Zahl, die durch φ dargestellt wird (ihr Wert liegt bei 1,618). Wenn du eine Fibonacci-Zahl durch die vorhergehende teilst, nähert sich das Verhältnis immer mehr φ an. Zum Beispiel:

5 ÷ 3 ≈ 1.666

8 ÷ 5 ≈ 1.6

13 ÷ 8 ≈ 1.625

Je weiter du gehst, desto näher kommt er an 1.618. Das ist kein Zufall - das Verhältnis taucht ganz natürlich in der Fibonacci-Folge auf, weil die Zahlen so wachsen.

Euklid beschrieb es erstmals im antiken Griechenland als das Verhältnis von Extremwert und Mittelwert. Seitdem wird es mit Mustern in der Natur, wie den Spiralen in Muscheln und Blumen, sowie in der Kunst und Architektur in Verbindung gebracht.

Goldener Schnitt in der Kunst

Der Goldene Schnitt in der Kunst. Quelle

Praktische Anwendungen der Fibonacci-Folge

Die Fibonacci-Folge zeigt sich auf überraschende Weise in vielen Bereichen. Konzentrieren wir uns auf zwei seiner bemerkenswertesten Anwendungen: seine Muster in der Natur und seine Verwendung in der Computerwissenschaft.

Fibonacci in der Natur

Du kannst die Fibonacci-Folge überall in der Natur sehen. Schau dir Blumen an - die Anzahl der Blütenblätter entspricht oft den Fibonacci-Zahlen. Gänseblümchen können zum Beispiel 34, 55 oder 89 Blütenblätter haben, und Lilien haben oft 3, 5 oder 8. Diese Muster helfen den Pflanzen, so zu wachsen, dass sie das Sonnenlicht und die Niederschläge optimal nutzen können.

Auch die Spiralen in Tannenzapfen und Sonnenblumen folgen den Fibonacci-Zahlen. Die Anordnung der Samen in einer Sonnenblume zum Beispiel entspricht der Reihenfolge. Es ist faszinierend, wie etwas so Einfaches wie das Addieren zweier Zahlen so viel von der natürlichen Welt beschreiben kann.

Fibonacci in der Informatik

Die Fibonacci-Folge spielt auch in Algorithmen und Datenstrukturen eine wichtige Rolle. Die Fibonacci-Zahlen werden zum Beispiel in Suchalgorithmen verwendet, um Probleme effizient in kleinere Teile zu zerlegen. Die Sequenz steckt sogar hinter den Fibonacci-Haufen, einer Art Datenstruktur, die dazu dient, bestimmte Operationen zu beschleunigen, z. B. den kürzesten Weg in einem Netzwerk zu finden.

Hier ist ein einfaches Beispiel, wie du eine Fibonacci-Folge in Python erzeugen kannst:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
for i in range(10):
    print(fibonacci(i), end=" ")
0 1 1 2 3 5 8 13 21 34

Diese rekursive Funktion zeigt, wie die Fibonacci-Folge aufgebaut ist. Während die Rekursion leicht zu verstehen ist, gibt es auch optimierte Versionen, wie die dynamische Programmierung, um Fibonacci-Zahlen viel schneller zu berechnen.

In der Kryptografie können Fibonacci-Zahlen helfen, sichere Schlüssel zu erzeugen. Und in der künstlichen Intelligenz optimieren sie neuronale Netze, um zu verbessern, wie Algorithmen lernen und sich anpassen. 

Andere gängige Beispiele

Hier sind noch ein paar weitere Beispiele, wie diese Reihenfolge im Alltag und in Fachgebieten vorkommt:

  • In Art: Die Fibonacci-Folge wird schon seit Jahrhunderten von Künstlern und Architekten verwendet. Berühmte Bauwerke wie der Parthenon weisen diese Proportionen auf, weil sie dem Auge natürlich schmeicheln.
  • In der Musik: Komponisten verwenden Fibonacci-Zahlen, um Rhythmen und Melodien zu kreieren. Sie ordnen zum Beispiel ganze Noten der 1, halbe Noten der 2 und Viertelnoten der 3 zu, um harmonische Muster zu schaffen.
  • Im Handel: Aktienhändler verwenden Fibonacci-Zahlen, um Markttrends zu analysieren. Sie nutzen sie, um potenzielle Kursniveaus vorherzusagen, auf denen Aktien umkehren könnten, und können so entscheiden, wann sie kaufen oder verkaufen sollten.
  • In der Physik: In der Quantenphysik wurden Fibonacci-Muster in den Interaktionen und im Verhalten von Teilchen beobachtet, was zeigt, dass diese Sequenzen selbst auf den kleinsten Skalen der Natur auftreten.

Implementierung der Fibonacci-Folge in Python

Da Python mehrere Möglichkeiten bietet, die Fibonacci-Folge zu erzeugen, habe ich die am häufigsten verwendeten Schritt für Schritt mit Beispielen erklärt.

Mit einer iterativen Methode

Die iterative Methode ist eine der einfachsten Methoden, um die Fibonacci-Folge zu erzeugen. Sie verwendet eine Schleife, um jeden Term in der Folge zu berechnen, was sie speichereffizienter macht als rekursive Methoden. So funktioniert es:

Ich setze zwei Variablen, a und b, auf 0 und 1. Diese stehen für die ersten beiden Zahlen in der Folge. Dann verwende ich eine for Schleife, um die nächsten Zahlen zu berechnen. Ich aktualisiere a, um den Wert von b zu erhalten, und b wird die Summe der vorherigen a und b.

Hier ist ein Python-Code für diese Aufgabe:

n = 10
a, b = 0, 1

for i in range(n):
    print(a)
    a, b = b, a + b
0
1
1
2
3
5
8
13
21
34

Wenn du eine while -Schleife statt einer for -Schleife verwenden möchtest, kannst du den Code folgendermaßen schreiben:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

while i < n:
    print(a, end=' ')
    # Update the terms
    a, b = b, a + b
    i += 1
0 1 1 2 3 5 8 13 21 34

Beide Methoden sind super einfach zu verstehen, was sie perfekt für Anfänger macht. 

Eine rekursive Methode verwenden

Die rekursive Methode ist eine weitere Möglichkeit, Fibonacci-Zahlen zu erzeugen. Es ist nicht so schnell wie die iterative Methode für größere Sequenzen, aber es ist ein guter Weg, um die Logik hinter dem Aufbau der Sequenz zu verstehen.

Ich erstelle zum Beispiel eine Funktion namens fibonacci_recursive. Diese Funktion nimmt eine Zahl n als Eingabe. Wenn n 0 oder 1 ist, gibt die Funktion n zurück. Dies sind die Basisfälle, die der Rekursion sagen, wann sie aufhören soll. Für jede andere Zahl ruft die Funktion sich selbst auf, um die beiden vorherigen Zahlen zu berechnen und addiert sie zusammen.

Hier ist der Code dafür:

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
for i in range(num_terms):
    print(fibonacci_recursive(i), end=" ")
0 1 1 2 3 5 8 13 21 34

Diese Methode funktioniert gut für kleine Sequenzen, kann aber langsam werden, wenn die Sequenz wächst, weil sie dieselben Werte mehrmals neu berechnet.

Verwendung einer optimierten rekursiven Methode mit Zwischenspeicherung

Um die Ineffizienz der einfachen Rekursion zu beheben, verwende ich oft Caching. Pythons lru_cache speichert bereits berechnete Werte, damit die Funktion die Arbeit nicht noch einmal machen muss.

So mache ich es:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")
The Fibonacci Number is 55.

Dieser Ansatz kombiniert die Klarheit der Rekursion mit der Effizienz des Caching.

Fortgeschrittene Möglichkeiten, die Fibonacci-Folge in Python zu berechnen

Wenn du nach anderen Möglichkeiten suchst, Fibonacci-Zahlen zu berechnen, findest du hier ein paar fortgeschrittenere Techniken:

Matrixpotenzierung

Die Matrixpotenzierung ist eine der effizientesten Methoden zur Berechnung von Fibonacci-Zahlen für große Werte von n. Anstatt die Terme immer wieder neu zu berechnen, verwendet diese Methode die Matrixmultiplikation, um die Ergebnisse in logarithmischer Zeit zu erhalten.

So habe ich das in Python umgesetzt:

import numpy as np

def fibonacci_matrix(n):
    def matrix_power(matrix, power):
        return np.linalg.matrix_power(matrix, power)
    
if n == 0:
        return 0
    matrix = np.array([[1, 1], [1, 0]])
    result = matrix_power(matrix, n-1)
    return result[0][0]
for i in range(10):
    print(fibonacci_matrix(i)  , end=" ")
0 1 1 2 3 5 8 13 21 34

Wenn in diesem Code n 0 ist , wird 0 als Basisfall zurückgegeben. Für andere Werte wird die Matrix mit der Funktion matrix_power von numpy hochgezählt (n-1). Die Fibonacci-Zahl an der Position n befindet sich im linken oberen Element der resultierenden Matrix.

Binet's Formel

Die Formel von Binet berechnet direkt die nth Fibonacci-Zahl ohne Iteration oder Rekursion. Sie basiert auf dem Goldenen Schnitt, φ, und verwendet einen mathematischen Ausdruck, um das Ergebnis sofort zu berechnen.

Die Formel lautet:

Binets Formel in der Fibonacci-Folge in Python.

Wo:

  • φ = (1 + 5) / 2​den goldenen Schnitt.
  • 1 - φ ist die Konjugierte von φ.

Hier ist der Python-Code für die Formel von Binet:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f" The Fibonacci Number of {n}th term is {result}" ) 
The Fibonacci number of 10th term is 55

In diesem Code berechnet die Funktion fibonacci_binet(n) die nth Fibonacci-Zahl mithilfe der Binet-Formel. In der Funktion berechne ich phi (den Goldenen Schnitt) als (1 + math.sqrt(5)) / 2 und verwende math.sqrt() für die Quadratwurzel aus 5. Die Formel (phi ** n - (1 - phi) ** n) / math.sqrt(5) wird dann angewendet, um die nth Fibonacci-Zahl direkt zu finden. Dann verwende ich die Funktion round(), um kleine Fließkomma-Ungenauigkeiten auszugleichen.

Arrays

Du kannst sogar Arrays verwenden, um die gesamte Fibonacci-Folge zu erzeugen und zu speichern. Das ist hilfreich, wenn du mehrere Begriffe gleichzeitig brauchst.

Hier ist der Code dafür:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")
Fibonacci number: 34

Backtracking

Backtracking ist eine weitere Option, die ich nutzen könnte, vor allem, wenn ich Rekursion mit Memoisierung für bessere Leistung kombinieren möchte.

Hier ist der Code dafür:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")
The 10th Fibonacci term is 55

Komplexität von Fibonacci-Algorithmen in Python

Wir haben schon einige Beispiele durchgespielt! Schauen wir uns nun ihre Unterschiede in Bezug auf die zeitliche und räumliche Komplexität an. Wie wir bereits erwähnt haben, sind einige Methoden schnell, benötigen aber mehr Speicherplatz, während andere langsamer sind, aber weniger Platz benötigen. Ich habe diese Tabelle erstellt, um die Effizienz der einzelnen Ansätze zu vergleichen.

Methode Zeitkomplexität Raumkomplexität
Iterativ (For-Schleife) O(n) O(1)
Iterativ (While-Schleife) O(n) O(1)
Einfache Rekursion O(2ⁿ) O(n)
Memoisierung/Caching O(n) O(n)
Array-basiert O(n) O(n)
Backtracking-Methode O(2ⁿ) O(2ⁿ)
Potenzierung der Matrix O(log n) O(log n)

In der obigen Tabelle siehst du, was die einzelnen Zeit- und Raumkomplexitäten bedeuten:

Zeitliche Komplexität

  • O(n): Der Algorithmus durchläuft die Sequenz einmal, indem er für jedes Element eine feste Anzahl von Operationen durchführt. Die benötigte Zeit wächst linear mit der Größe der Eingabe n.

  • O(1): Die Fibonacci-Zahl wird mit einer festen Anzahl von Operationen ohne Iteration oder Rekursion berechnet.

  • O(2n): Der Algorithmus macht zwei rekursive Aufrufe für jede Eingabe, was zu einem exponentiellen Wachstum der Anzahl der Funktionsaufrufe führt, wenn n steigt.

  • O(log n): Die Laufzeit wächst proportional zum Logarithmus der Eingabegröße n.

Raumkomplexität

  • O(n): Der Algorithmus verwendet Speicher, der direkt mit der Anzahl der Eingaben n wächst. Hier benötigt jedes Element eine bestimmte Menge an Platz.

  • O(1): Der Speicherverbrauch bleibt unabhängig von der Eingabegröße konstant.

  • O(2n): Sie verbraucht exponentiell viel Platz, da für jeden Zweig neue Zustände erzeugt werden.

  • O(log n): Zwischenmultiplikationen von Matrizen verwenden logarithmischen Speicher.

Schlussgedanken

Wie du gesehen hast, kannst du in Python Fibonacci-Zahlen mit vielen verschiedenen Methoden berechnen, von einfachen Schleifen bis hin zu fortgeschrittenen Techniken wie der Matrixexponentierung und der Binet-Formel. Jede Methode hat ihre Stärken und Schwächen.

Ich hoffe, du hast nicht nur etwas über die Fibonacci-Folge gelernt, sondern auch über die Programmierung mit Python. Wenn du mehr über Python und verwandte Themen erfahren möchtest, schau dir unseren Kurs "Einführung in Python " an. Du kannst auch unseren kompletten Lernpfad für Python-Entwickler/innen ausprobieren, um Programmiertechniken zu erlernen und sogar eigene Pakete zu entwickeln!


Laiba Siddiqui's photo
Author
Laiba Siddiqui
LinkedIn
Twitter

Ich bin ein Inhaltsstratege, der es liebt, komplexe Themen zu vereinfachen. Ich habe Unternehmen wie Splunk, Hackernoon und Tiiny Host geholfen, ansprechende und informative Inhalte für ihr Publikum zu erstellen.

Fibonacci-Sequenz in Python FAQs

Wofür wird die Fibonacci-Folge verwendet?

Die Fibonacci-Folge wird in verschiedenen Bereichen wie der Mathematik, der Informatik und den Naturwissenschaften verwendet, um Wachstumsmuster zu modellieren und Algorithmen zu optimieren.

Wie wird die Fibonacci-Folge berechnet?

Die Fibonacci-Folge wird berechnet, indem die beiden vorhergehenden Zahlen addiert werden, um die nächste Zahl zu erhalten, beginnend mit 0 und 1.

Was sind Beispiele für die Fibonacci-Folge in der Natur?

Beispiele dafür sind die Anordnung der Blätter an einem Stamm, die Verzweigung von Bäumen und das Muster verschiedener Früchte und Blüten.

Wie kann man die Fibonacci-Folge in Python implementieren?

Du kannst sie entweder iterativ oder rekursiv implementieren. Beispiele für Python-Code findest du in vielen Programmier-Tutorials.

Wie lautet die Formel für den n-ten Term der Fibonacci-Folge?

Der n-te Term kann mit der Binet-Formel berechnet werden, die den Goldenen Schnitt beinhaltet und eine direkte Berechnungsmethode bietet.

Themen

Lerne Python mit DataCamp

Kurs

Introduction to Python

4 hr
6M
Master the basics of data analysis with Python in just four hours. This online course will introduce the Python interface and explore popular packages.
Siehe DetailsRight Arrow
Kurs starten
Mehr anzeigenRight Arrow
Verwandt

Der Blog

Q2 2023 DataCamp Donates Digest

DataCamp Donates hat im zweiten Quartal 2023 über 20.000 Stipendien an unsere gemeinnützigen Partner vergeben. Erfahre, wie fleißige benachteiligte Lernende diese Chancen in lebensverändernde berufliche Erfolge verwandelt haben.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

Der Blog

Lehrer/innen und Schüler/innen erhalten das Premium DataCamp kostenlos für ihre gesamte akademische Laufbahn

Keine Hacks, keine Tricks. Schüler/innen und Lehrer/innen, lest weiter, um zu erfahren, wie ihr die Datenerziehung, die euch zusteht, kostenlos bekommen könnt.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

4 Min.

Der Blog

Die 20 besten Snowflake-Interview-Fragen für alle Niveaus

Bist du gerade auf der Suche nach einem Job, der Snowflake nutzt? Bereite dich mit diesen 20 besten Snowflake-Interview-Fragen vor, damit du den Job bekommst!
Nisha Arya Ahmed's photo

Nisha Arya Ahmed

20 Min.

Der Blog

2022-2023 DataCamp Classrooms Jahresbericht

Zu Beginn des neuen Schuljahres ist DataCamp Classrooms motivierter denn je, das Lernen mit Daten zu demokratisieren. In den letzten 12 Monaten sind über 7.650 neue Klassenzimmer hinzugekommen.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

8 Min.

Der Blog

Die 32 besten AWS-Interview-Fragen und Antworten für 2024

Ein kompletter Leitfaden zur Erkundung der grundlegenden, mittleren und fortgeschrittenen AWS-Interview-Fragen, zusammen mit Fragen, die auf realen Situationen basieren. Es deckt alle Bereiche ab und sorgt so für eine abgerundete Vorbereitungsstrategie.
Zoumana Keita 's photo

Zoumana Keita

30 Min.

Der Blog

Top 30 Generative KI Interview Fragen und Antworten für 2024

Dieser Blog bietet eine umfassende Sammlung von Fragen und Antworten zu generativen KI-Interviews, die von grundlegenden Konzepten bis hin zu fortgeschrittenen Themen reichen.
Hesam Sheikh Hassani's photo

Hesam Sheikh Hassani

15 Min.

Mehr anzeigenMehr anzeigen