NWD odejmowaniem

Algorytm Euklidesa iteracyjnie: odejmowanie i reszta z dzielenia - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

**Największy wspólny dzielnik** NWD(a, b) to największa liczba, przez którą dzielą się obie liczby. Euklides zauważył, że wspólne dzielniki `a` i `b` (dla `a > b`) są takie same jak wspólne dzielniki `a - b` i `b`. Wystarczy więc od większej liczby odejmować mniejszą, aż obie będą równe: ta wartość to NWD. Specyfikacja: - dane: liczby całkowite dodatnie `a`, `b`, - wynik: NWD(a, b). Program liczy też **kroki** (odejmowania). Kliknij **Krok** i patrz, jak maleją `a` i `b`.

def gcd_sub(a, b):
    steps = 0
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
        steps += 1
    return a, steps

print(gcd_sub(48, 18))
print(gcd_sub(17, 5))
print(gcd_sub(1000, 3))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 1, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.