Przejdź do treści

NWD

Opis problemu

Algorytm NWD z odejmowaniem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def gcd(a: int, b: int) -> int:
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a

    return a

a = 32
b = 12

result = gcd(a, b)

print(f"GCD({a}, {b}) = {result}")

Algorytm Euklidesa - wersja iteracyjna

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b

    return a

a = 32
b = 12

result = gcd(a, b)

print(f"GCD({a},{b}) = {result}")

Algorytm Euklidesa - wersja rekurencyjna

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def gcd(a: int, b: int) -> int:
    if b == 0:
        return a

    return gcd(b, a % b)

a = 32
b = 12

result = gcd(a, b)

print(f"GCD({a},{b}) = {result}")