Ciąg Fibonacciego
W tym ćwiczeniu zaimplementujesz ciąg Fibonacciego, który pojawia się w naturze niemal wszędzie. Ciąg wygląda następująco: "0, 1, 1, 2, 3, 5, 8…". Stworzysz rekurencyjną implementację algorytmu generującego ten ciąg.
Pierwsze dwie liczby to 0 i 1, a każda kolejna jest sumą dwóch poprzednich.
Ciąg można zdefiniować rekurencyjnie jako: \(fib(n)=fib(n-1)+fib(n-2)\), gdzie \(fib(0)=0\) i \(fib(1)=1\), a \(n\) oznacza \(n\)-tą pozycję w ciągu.
W pierwszym kroku zkodujesz ciąg Fibonacciego przy użyciu rekurencji. W drugim kroku ulepszysz rozwiązanie, stosując programowanie dynamiczne – wyniki podproblemów będziesz zapisywać w zmiennej cache.
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))