Połowienie wykładnika

Szybkie potęgowanie rekurencyjnie - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Naiwne potęgowanie `xⁿ = x · x · ... · x` wykonuje `n - 1` mnożeń. Szybciej: - gdy `n` jest parzyste, `xⁿ = (x^(n/2))²` - wystarczy policzyć potęgę o połowę mniejszą i podnieść ją do kwadratu (jedno mnożenie), - gdy `n` jest nieparzyste, `xⁿ = x · xⁿ⁻¹`, - `x⁰ = 1`. Wykładnik maleje co najmniej o połowę co dwa kroki, więc mnożeń jest około `2 log₂ n`. Ważne: wynik połowy liczy się **raz** i zapamiętuje w zmiennej (`half * half`), a nie wywołuje funkcji dwa razy.

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

for n in [0, 1, 10, 13]:
    print("2 **", n, "=", fast_power(2, n))

Ł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.