Przejdź do treści

Szybkie potęgowanie

Opis problemu

Rozwiązanie iteracyjne

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def fast_exp(a: int, n: int) -> int:
    w = 1

    while n > 0:
        if n % 2 == 1:
            w *= a

        a *= a
        n = n // 2

    return w

a = 2
n = 10

result = fast_exp(a, n)

print(f"{a}^{n} = {result}")

Rozwiązanie rekurencyjne

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def fast_exp(a: int, n : int) -> int:
    if n == 0:
        return 1

    if n % 2 == 1:
        return fast_exp(a, n // 2) ** 2 * a
    else:
        return fast_exp(a, n // 2) ** 2

a = 2
n = 10

result = fast_exp(a, n)

print(f"{a}^{n} = {result}")