Fibonacciho posloupnost
V tomto cvičení implementuješ Fibonacciho posloupnost, která se hojně vyskytuje v přírodě. Posloupnost vypadá takto: „0, 1, 1, 2, 3, 5, 8…". Vytvoříš rekurzivní implementaci algoritmu, který tuto posloupnost generuje.
První dvě čísla jsou 0 a 1, každé další je součtem dvou předchozích čísel.
Tuto posloupnost můžeme rekurzivně definovat jako: \(fib(n)=fib(n-1)+fib(n-2)\), kde \(fib(0)=0\) a \(fib(1)=1\), přičemž \(n\) označuje \(n\)-tou pozici v posloupnosti.
V prvním kroku napíšeš Fibonacciho posloupnost pomocí rekurze. Ve druhém kroku ji vylepšíš pomocí dynamického programování – řešení dílčích problémů budeš ukládat do proměnné cache.
Toto cvičení je součástí kurzu
Datové struktury a algoritmy v Pythonu
Interaktivní cvičení na vyzkoušení si v praxi
Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))