Przypomnienie: rekurencja i szybkie potęgowanie

Sprawdzian: rekurencja i dziel i zwyciężaj - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Funkcja rekurencyjna ma **przypadek bazowy** (bez wywołania) i **krok rekurencyjny** (wywołanie dla mniejszych danych). Szybkie potęgowanie: `a⁰ = 1`, dla parzystego `n` `aⁿ = (a^(n/2))²`, dla nieparzystego `aⁿ = a · aⁿ⁻¹` - około `2 log₂ n` mnożeń.

def power(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power(a, n // 2)
        return half * half
    return a * power(a, n - 1)

print(power(3, 13), power(2, 100) % 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.