Algorytm Euklidesa: NWD w Pythonie i C++

Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba, przez którą obie dzielą się bez reszty. NWD(48, 18) = 6, bo 48 = 6 * 8 i 18 = 6 * 3, a żadna większa liczba nie dzieli obu. Algorytm Euklidesa liczy NWD bez szukania dzielników: to jeden z najstarszych algorytmów (ok. 300 r. p.n.e.) i jeden z pierwszych, które poznaje się w szkole.

Na tej stronie znajdziesz obie wersje algorytmu (z odejmowaniem i z resztą z dzielenia), NWW, skracanie ułamków i kod w Pythonie oraz C++. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź algorytm Euklidesa krok po kroku

Idea: mniejsza para, ten sam NWD

Kluczowa obserwacja: jeśli liczba d dzieli a i b, to dzieli też ich różnicę a - b. Dlatego para (a, b) i para (a - b, b) mają ten sam NWD. Zamieniając większą liczbę na różnicę, dostajemy coraz mniejsze liczby, a NWD się nie zmienia. Gdy obie liczby staną się równe, ta wspólna wartość jest NWD.

Wersja z odejmowaniem

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

Prześledźmy wartości zmiennych:

Wynik: NWD = 6. Ta wersja jest prosta do zrozumienia, ale ma wadę: gdy jedna liczba jest dużo większa od drugiej, odejmuje tę samą liczbę bardzo wiele razy. Dla pary (1000, 7) pętla obraca się 148 razy. Uwaga też na zero: dla b = 0 pętla nigdy się nie kończy, bo a - 0 = a.

Krokuj wersję z odejmowaniem

Wersja z resztą z dzielenia (modulo)

Odjęcie b od a tyle razy, ile się da, to po prostu reszta z dzielenia a przez b. Szybsza wersja zamienia więc parę (a, b) na (b, a % b) i kończy, gdy druga liczba spadnie do zera:

a = 48
b = 18
while b != 0:
    reszta = a % b
    a = b
    b = reszta
print("NWD =", a)

Trzy obroty pętli zamiast czterech, a dla pary (1000, 7) trzy zamiast 148. Liczba kroków tej wersji rośnie bardzo wolno (jak logarytm z mniejszej liczby), więc algorytm jest szybki nawet dla liczb o setkach cyfr. To tę wersję warto pisać na sprawdzianie i maturze. Dobrze działa też dla b = 0: wynikiem jest a.

W Pythonie zamianę można zapisać jednym przypisaniem krotki: a, b = b, a % b. Prawa strona liczy się w całości przed przypisaniem, więc nie potrzeba zmiennej reszta.

Krokuj wersję z modulo

Algorytm Euklidesa w C++

W C++ wersja z modulo wygląda prawie tak samo. Zamknięta w funkcji nadaje się do wielokrotnego użycia:

#include <iostream>
using namespace std;

int nwd(int a, int b) {
  while (b != 0) {
    int reszta = a % b;
    a = b;
    b = reszta;
  }
  return a;
}

int main() {
  cout << nwd(48, 18) << endl;
  cout << nwd(1000, 7) << endl;
  cout << nwd(84, 36) << endl;
  return 0;
}

6
1
12

Algorytm Euklidesa ma też naturalną postać rekurencyjną: NWD(a, 0) = a, a NWD(a, b) = NWD(b, a % b). W C++:

#include <iostream>
using namespace std;

int nwd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return nwd(b, a % b);
}

int main() {
  cout << nwd(48, 18) << endl;
  return 0;
}

6

NWW i skracanie ułamków

Z NWD od razu wynika najmniejsza wspólna wielokrotność: NWW(a, b) = a * b / NWD(a, b). NWW(12, 18) = 216 / 6 = 36.

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def nww(a, b):
    return a * b // nwd(a, b)


print(nww(12, 18))
print(nww(4, 6))

36
12

W C++ iloczyn dużych liczb może nie zmieścić się w typie int, dlatego bezpieczniej liczyć a / nwd(a, b) * b. W Pythonie liczby całkowite nie mają limitu.

Skracanie ułamka to podzielenie licznika i mianownika przez ich NWD: 84/126 skraca się przez NWD(84, 126) = 42 do 2/3. NWD trzech liczb liczy się dwa razy: NWD(a, b, c) = NWD(NWD(a, b), c).

Ćwicz: skracanie ułamka

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Algorytm Euklidesa z odejmowaniem

Specyfikacja. Dane: liczby naturalne dodatnie a i b. Wynik: NWD(a, b), największy wspólny dzielnik a i b.

Lista kroków:

1. Wczytaj liczby a i b.
2. Jeśli a = b, przejdź do kroku 5.
3. Jeśli a > b, zastąp a różnicą a - b. W przeciwnym razie zastąp b różnicą b - a.
4. Wróć do kroku 2.
5. Wypisz a (to NWD) i zakończ.

Pseudokod:

wczytaj a, b
dopóki a ≠ b wykonuj
  jeżeli a > b to
    a ← a - b
  w przeciwnym razie
    b ← b - a
wypisz a

Schemat blokowy:

Algorytm Euklidesa z resztą z dzielenia

Specyfikacja. Dane: liczby naturalne a i b, a > 0. Wynik: NWD(a, b).

Lista kroków:

1. Wczytaj liczby a i b.
2. Jeśli b = 0, przejdź do kroku 6.
3. Oblicz r, resztę z dzielenia a przez b.
4. Zastąp a liczbą b, a b liczbą r.
5. Wróć do kroku 2.
6. Wypisz a (to NWD) i zakończ.

Pseudokod:

wczytaj a, b
dopóki b ≠ 0 wykonuj
  r ← a mod b
  a ← b
  b ← r
wypisz a

Schemat blokowy:

Najczęstsze błędy

• Zła kolejność przypisań. a = b a potem b = a % b liczy resztę już z nowego a (czyli b % b = 0) i kończy po jednym kroku z błędnym wynikiem. Najpierw zapamiętaj resztę, albo w Pythonie użyj a, b = b, a % b.
• Zero w wersji z odejmowaniem. Dla b = 0 pętla while a != b się nie kończy. Wersja z modulo zwraca wtedy poprawnie a.
• Zły warunek pętli. W wersji z modulo kończymy, gdy b == 0, a wynikiem jest a, nie b.
• Przepełnienie przy NWW w C++. a * b dla liczb rzędu 100 000 nie mieści się w int. Dziel przed mnożeniem albo użyj long long.

Ćwicz w przeglądarce

W temacie “Algorytm Euklidesa: NWD i NWW” kursu Algorytmy z podstawy programowej czekają trzy przykłady do krokowania i cztery zadania, które sprawdzają się automatycznie po uruchomieniu:

• NWD dwóch liczb wersją z modulo,
• skracanie ułamka,
• NWD trzech liczb,
• porównanie liczby kroków obu wersji.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości a i b. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Dalsze algorytmy z tego samego kursu: liczby pierwsze i sito Eratostenesa oraz systemy liczbowe. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Algorytm Euklidesa to dobry pierwszy algorytm “z historią”: uczniowie widzą, że ten sam wynik można policzyć wolniej i szybciej, i mogą to zmierzyć licznikiem kroków. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.