Wyznaczanie NWD i NWW dla dwóch liczb naturalnych (algorytm Euklidesa)
------------------------------------------------------------------------------------------------------

Jednym z klasycznych algorytmów jest algorytm znajdowania największego wspólnego dzielnika dla pary

liczb naturalnych. Największy wspólny dzielnik dwóch liczb całkowitych a i b oznaczamy symbolem
NWD(a, b). Umiejętność znajdowania największego wspólnego dzielnika przydaje się zwłaszcza w sytuacji,
gdy chcemy skrócić ułamek, co oznacza podzielenie licznika i mianownika przez ich największy wspólny
dzielnik. Otrzymujemy wówczas ułamek już dalej nieskracalny, gdyż w liczniku i mianowniku znajdują się
tak zwane liczby względnie pierwsze, czyli takie, których największy wspólny dzielnik wynosi 1.

Największym wspólnym dzielnikiem dwóch liczb naturalnych jest największa z liczb
całkowitych, przez którą obie liczby dzielą się bez reszty.

Jak znaleźć największy wspólny dzielnik dwóch liczb za pomocą prostego algorytmu? Można by na przykład

sprawdzać, począwszy od wartości mniejszej z dwóch badanych liczb, czy obie dzielą się przez nią bez reszty.
Następnie, jeśli tak nie jest, dzielnik zmniejszyć o 1 i znów badać, czy obie liczby dzielą się przez nowy
dzielnik. Postępujemy w ten sposób tak długo, aż znajdziemy wartość, która dzieli obie liczby bez reszty.
Będzie to ich największy wspólny dzielnik. Opisaną metodę można zakwalifikować do metod zwanych
metodami brutalnymi (ang. brute force), ponieważ jest bardzo prosta, ale wymaga wykonania wielu operacji.
Dlatego warto poznać algorytm szybszy, a jednocześnie równie prosty w implementacji. Nosi on nazwę
pochodzącą od nazwiska jego twórcy: algorytm Euklidesa. Zacznijmy od słownego opisu algorytmu.

Pobieramy dwie liczby, dla których chcemy wyznaczyć największy wspólny dzielnik. Od większej z nich

odejmujemy mniejszą, a następnie większą liczbę zastępujemy otrzymaną różnicą. Postępujemy tak dotąd, aż liczby
będą równe. Otrzymana liczba jest największym wspólnym dzielnikiem.

Zanim zapiszemy sformalizowany algorytm, przeanalizujmy przykład liczbowy:

Niech

liczba

a ma wartość 12, a liczba b wartość 20. Ponieważ b > a, więc liczbę b zastępujemy różnicą b - a,

czyli nowe b przyjmie wartość 8. Mamy zatem dane a = 12 oraz b = 8. Teraz a > b, więc tym razem zastępujemy a róż-
nicą a - b, czyli liczbą 4. Ponieważ a ma wartość 4, a b jest równe 8, więc w miejsce b wstawimy b - a, czyli 4.
Otrzymaliśmy warunek zakończenia pętli, gdyż obie liczby są już sobie równe. A zatem szukany NWD to liczba 4.

-------------------------------------------------------------------------------------------------------------------------------------------------

Przykład 1

Napiszmy program, który dla dwóch liczb a, b podanych na wejściu oblicza ich NWD (klasyczna metoda

Euklidesa).

-------------------------------------------------------------------------------------------------------------------------------------------------

Przejdźmy do formalnego opisu algorytmu.

Specyfikacja problemu algorytmicznego

Problem algorytmiczny:

Wyznaczenie największego wspólnego
dzielnika dwóch liczb

Dane wejściowe:



 N

b

a,

Dane wyjściowe:

NWD(a, b)

Kolejno postępujemy według listy kroków:

1. Wczytaj a, b.
2. Jeśli a = b, wypisz a i zakończ.
3. Jeśli a > b, zmiennej a przypisz a - b i wróć do kroku 2.
4. Jeśli a < b, zmiennej b przypisz b - a i wróć do kroku 2.

Tak skonstruowany algorytm Euklidesa opiera się na własności:
NWD(a, b) = NWD(a - b, b), jeśli a > b
NWD(a, 6) = NWD(a, b - a), jeśli b > a
Przeanalizujmy jeszcze schemat blokowy algorytmu:

Ryc. Schemat blokowy algorytmu wyznaczającego NWD dwóch liczb metodą Euklidesa

Kod samego algorytmu jest krótki i przejrzysty, nie powinno zatem być problemu z jego zrozumieniem:

-------------------------------------------------------------------------------------------------------------------------------------------------

Przykład 2

Napiszmy program, który podobnie jak poprzedni, dla dwóch liczb a, b oblicza ich NWD (zoptymalizowana

metoda Euklidesa).

-------------------------------------------------------------------------------------------------------------------------------------------------

Częściej stosuje się modyfikację algorytmu Euklidesa, wykorzystującą zależność: NWD (a, b) = NWD (a

mod b,b-(a mod b)).

Będziemy iteracyjnie zmieniać wartości liczb a i b aż do momentu, gdy a osiągnie wartość 0. Wówczas

największy wspólny dzielnik obu liczb wynosi b. Jest to oczywiste, gdyż 0 dzieli się przez każdą liczbę całkowitą,
a największą z liczb, przez jaką dzieli się liczba różna od 0, jest ona sama. Stąd: NWD(0, b) = b.

Zapiszmy algorytm jako listę kroków:

1. Wczytaj a, b.
2. Jeśli a nie jest większe od 0, wypisz b i zakończ.
3. Zmiennej a przypisz resztę z dzielenia a przez b.
4. Zmiennej b przypisz różnicę b - a i wróć do kroku 2.

Spójrzmy na gotowy schemat blokowy:

Funkcja obliczająca NWD według tej metody ma postać:

int NWD(int a, int b)

{

while (a>0)

{

a = a%b;

b = b-a;

}

return b;

}

-----------------------------------------------------------------------------------------------------------------------------------
Dla porównania obu metod prześledźmy ilość pętli wykonujących się w algorytmach podczas szukania

NWD dla dwóch dowolnych liczb.

Pierwsza z metod Euklidesa:

Ryc. Schemat blokowy algorytmu wyznaczającego NWD dwóch liczb zoptymalizowaną

metodą Euklidesa

NWD(51,60) = NWD(51,9) = NWD(42,9) = NWD(33,9) = NWD(24,9) = = NWD(15,9) = NWD(6,9) =
NWD(6,3) = NWD(3,3)

Druga z metod Euklidesa:
NWD(51,60) = NWD(51,9) = NWD(6,3) = NWD(0,3)

Jak widać, dla tak dobranych liczb różnica w ilości wykonanych operacji jest duża. Czy oznacza to, że druga z

metod jest szybsza? Nie w każdym przypadku. Weźmy inny zestaw liczb, dla których poszukamy NWD według obu
metod.

Pierwsza z metod Euklidesa:
NWD(12, 48) = NWD(12, 36) = NWD(12, 24) = NWD(12, 12)

Druga z metod Euklidesa:

NWD(12, 48) = NWD(12, 36) = NWD(12, 24) = NWD(12, 12) = = NWD(0, 12)

Druga z metod zdecydowanie zmniejsza ilość obiegów pętli w wypadku, gdy mamy do czynienia z parą liczb

względnie pierwszych lub kiedy największym wspólnym dzielnikiem jest liczba stosunkowo mała.

W starszych procesorach ten fakt nie miał większego znaczenia, ponieważ operacje dzielenia

(wykorzystywane w drugiej z metod) były znacznie bardziej skomplikowane niż odejmowanie. W najnowszych
procesorach to się zmieniło, dlatego częściej stosuje się drugą z metod.

-------------------------------------------------------------------------------------------------------------------------------------------------

Przykład

Poszukajmy najmniejszej wspólnej wielokrotności dwóch liczb (wykorzystanie algorytmu Euklidesa).

-------------------------------------------------------------------------------------------------------------------------------------------------

Najmniejszą wspólną wielokrotnością dwóch liczb naturalnych nazywamy najmniejszą z
liczb, która jest podzielna przez obie te liczby.

Najmniejszą wspólną wielokrotność liczb a l b w skrócie oznaczamy jako NWW(a, b). Wyznaczenie jej ma

zastosowanie na przykład przy sprowadzaniu ułamków do wspólnego mianownika.

Nie będziemy

konstruować nowego algorytmu do znajdowania NWW(fl, b),

ponieważ

w istocie opiera się

on na algorytmie znajdowania NWD i

wzorze:

NWW<a, b) = (a * b) div NWD(a, b)

gdzie div oznacza dzielenie w zbiorze liczb całkowitych. W języku C++ dzielenie

w

zbiorze liczb

całkowitych jest automatycznie realizowane

przez

operator dzielenia /,

jeśli

dzielna i dzielnik są liczbami cał-

kowitymi, na przykład jeśli a =

5,

6

= 2

i obydwie

są

zmiennymi typu int, to a

I

b — 2.