Fibonacci: rekurencja z zapamiętywaniem

Programowanie dynamiczne - Algorytmy: zakres rozszerzony (Python)

Rekurencyjny Fibonacci liczy te same wartości wiele razy: F(30) wywołuje funkcję ponad 2,6 miliona razy. Jeśli zapamiętamy już policzone wyniki w słowniku, każdą wartość liczymy raz. To **metoda zstępująca** programowania dynamicznego: od dużego problemu w dół, do podproblemów.

calls = 0
memory = {}


def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    if n not in memory:
        memory[n] = fib(n - 1) + fib(n - 2)
    return memory[n]


print("F(30) =", fib(30))
print("wywołania:", calls)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.