Algorytm Euklidesa z odejmowaniem

Algorytm Euklidesa: NWD i NWW - Algorytmy z podstawy programowej (Python)

**Największy wspólny dzielnik** (NWD) dwóch liczb to największa liczba, przez którą dzielą się obie bez reszty. NWD(48, 18) = 6. Najstarsza wersja algorytmu Euklidesa korzysta z obserwacji: NWD(a, b) = NWD(a - b, b), gdy a > b. Odejmujemy więc mniejszą liczbę od większej tak długo, aż obie będą równe. Ta wspólna wartość to NWD. Przejdź program przyciskiem **Krok** i obserwuj w podglądzie, jak zmieniają się zmienne `a` i `b` w każdym obrocie pętli.

a = 48
b = 18
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
    print(a, b)
print("NWD =", a)

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

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.