Fibonacci-Folge
In dieser Übung wirst du die Fibonacci-Folge umsetzen, die in der Natur allgegenwärtig ist. Die Reihenfolge sieht wie folgt aus: "0, 1, 1, 2, 3, 5, 8…". Du wirst eine rekursive Implementierung eines Algorithmus erstellen, der die Sequenz erzeugt.
Die ersten Zahlen sind 0 und 1 und der Rest ist die Summe der beiden vorangegangenen Zahlen.
Wir können diese Folge rekursiv definieren als: \(fib(n)=fib(n-1)+fib(n-2)\), with \(fib(0)=0\) und \(fib(1)=1\), being \(n\) die \(nth\) Position in der Folge.
Im ersten Schritt wirst du Fibonacci mithilfe von Rekursion codieren. Im zweiten Schritt verbesserst du es mit Hilfe der dynamischen Programmierung, indem du die Lösungen der Teilprobleme in der Variablen cache speicherst.
Diese Übung ist Teil des Kurses
Datenstrukturen und Algorithmen in Python
Interaktive Übung
Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))