Te same podproblemy wiele razy

Programowanie dynamiczne: zapamiętywanie wyników podproblemów - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

Rekurencyjny Fibonacci `fib(n) = fib(n - 1) + fib(n - 2)` liczy te same wartości wiele razy: `fib(3)` pojawia się w drzewie wywołań `fib(6)` trzy razy. Liczba wywołań rośnie wykładniczo. Program liczy wywołania licznikiem w słowniku.

calls = {}

def fib(n):
    calls[n] = calls.get(n, 0) + 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(15))
print("wywołań razem:", sum(calls.values()))
print("ile razy fib(3):", calls[3])

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

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.