Fibonacci-Sequenz in Python: Kodierungstechniken lernen und erforschen

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.

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:

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.

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(2ⁿ): 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(2ⁿ): 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!