Szybkie potęgowanie rekurencyjnie

Szybkie potęgowanie - Algorytmy: zakres rozszerzony (Python)

Spostrzeżenie: a^n = (a^(n/2))^2 dla parzystego n, a dla nieparzystego trzeba jeszcze raz pomnożyć przez a. Każde wywołanie dzieli wykładnik na pół, więc wywołań jest tyle, ile cyfr ma wykładnik w systemie dwójkowym. Krokuj program i zobacz, jak na stosie wywołań maleje `n`.

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


print(fast_power(3, 13))
print(fast_power(2, 100))

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