1. Učit se
    2. /
  2. Kurzy
    3. /
  3. Datové struktury a algoritmy v Pythonu
Connected

Cvičení

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.

Pokyny 1/2

undefined XP
  • 1
    • Definuj základní případ.
    • Zavolej funkci fibonacci() rekurzivně.
  • 2
    • Zkontroluj, jestli hodnota existuje v cache.
    • Ulož výsledek do cache, aby nebylo nutné ho počítat znovu.