1. Nauka
    2. /
  2. Kursy
    3. /
  3. Struktury danych i algorytmy w Pythonie
Connected

ćwiczenie

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.

Instrukcje 1/2

undefined XP
  • 1
    • Zdefiniuj przypadek bazowy.
    • Wywołaj funkcję fibonacci() rekurencyjnie.
  • 2
    • Sprawdź, czy wartość istnieje w cache.
    • Zapisz wynik w cache, aby uniknąć ponownego przeliczania.