Euklides: odejmowanie i reszta

Algorytm Euklidesa rekurencyjnie i jego zastosowania - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

**Algorytm Euklidesa** liczy największy wspólny dzielnik (NWD) dwóch liczb naturalnych. Wersja z odejmowaniem: dopóki liczby są różne, od większej odejmij mniejszą. Wersja z resztą jest szybsza: zamieniaj parę `(a, b)` na `(b, a % b)`, aż `b` będzie zerem; wtedy NWD to `a`. Program liczy NWD(1071, 462) obiema metodami i wypisuje kolejne pary w wersji z resztą. Zwróć uwagę, ile kroków potrzeba w każdej wersji.

a, b = 1071, 462
steps = 0
while a != b:
    if a > b:
        a -= b
    else:
        b -= a
    steps += 1
print("odejmowanie:", a, "kroków:", steps)

a, b = 1071, 462
while b != 0:
    print(a, b)
    a, b = b, a % b
print("reszta:", a)

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