Rok w pigułce: rekurencja

Podsumowanie roku: metody algorytmiczne zakresu rozszerzonego - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Rekurencja: przypadek bazowy + wywołanie dla mniejszych danych. Z zapamiętywaniem wyników (metoda zstępująca) albo pętlą od przypadków bazowych (wstępująca) unika się wielokrotnego liczenia tego samego. Szybkie potęgowanie połowi wykładnik.

memo = {}

def paths(r, c):
    if r == 0 or c == 0:
        return 1
    if (r, c) not in memo:
        memo[(r, c)] = paths(r - 1, c) + paths(r, c - 1)
    return memo[(r, c)]

print(paths(10, 10), pow(3, 1000, 1000))

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

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