Algorytm Euklidesa

Przypomnijmy: algorytm Euklidesa stosowany jest do wyznaczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych. NWD może być wykorzystany do skracania ułamków czy obliczania najmniejszej wspólnej wielokrotności (NWW). Więcej na temat tego algorytmu przeczytasz w tym podręczniku w e‑materiale: Algorytm Euklidesa.

Specyfikacja problemu:

Dane

• a – liczba naturalna

• b – liczba naturalna

Wynik

• NWD liczb a i b

Algorytm Euklidesa z odejmowaniem

Wersja rekurencyjna prezentuje się następująco:

funkcja NWD(a, b)
	jeżeli a != b:
		jeżeli a > b 
        	zwróć NWD(a - b, b)
		w przeciwnym razie
        	zwróć NWD(a, b - a)
	zwróć a

Funkcje są rekurencyjnie wywoływane do momentu, gdy wartości argumentów funkcji będą takie same. Wtedy zwracana jest wartość jednego z nich i to on jest największym wspólnym dzielnikiem liczb a oraz b.

Algorytm Euklidesa opiera się na prostej obserwacji: jeżeli liczba naturalna c dzieli liczby naturalne a i b, to dzieli również ich różnicę. Rzeczywiście jeśli c = NWD(a, b), wówczas istnieją takie względnie pierwsze liczby naturalne k i l, dla których a = c * k oraz b = c * l. Niech ponadto a > b. Wówczas a - b = c * k - c * l = c * (k - l), co oznacza, że liczba a - b również dzieli się przez c. To oznacza, że zarówno różnica liczb b oraz a - b, jak i różnica liczb a oraz a - b dzielą się przez c. Powtarzanie odejmowania doprowadzi do obliczenia c.

Algorytm Euklidesa z resztą z dzielenia

W tym wariancie algorytmu do znalezienia NWD – zamiast różnicy dwóch liczb – używa się reszty z ich dzielenia.

W podejściu rekurencyjnym dla b różnego od 0 przykładowa funkcja NWD(a, b) wywołuje samą siebie z argumentami NWD(b, a mod b) do momentu trafienia na przypadek podstawowy, kiedy b będzie równe 0. Pseudokod takiej funkcji wygląda następująco:

funkcja NWD(a, b):
	jeżeli a != 0:
    	zwróć NWD(b mod a, a)
    w przeciwnym razie
    	zwróć b

Funkcje są rekurencyjnie wywoływane do momentu, gdy wartość jednego argumentu funkcji jest równa 0. Wtedy zwracana jest wartość jednego z nich i to on jest największym wspólnym dzielnikiem liczb a oraz b.

Zastanówmy się, dlaczego możemy w ten sposób podejść do tego problemu.

Załóżmy, że chcemy obliczyć NWD dwóch liczb a oraz b. Są to liczby naturalne. Chcemy wyznaczyć liczbę c, która jest ich największym wspólnym dzielnikiem.

W naszym problemie a ≤ b. Podzielmy b przez a. Otrzymamy iloraz (x) oraz resztę (r). Zapiszmy to.

$b ÷ a = x reszta r$

Zatem:

$b = ax + r$

natomiast:

$0 \le r < m$

Jeśli r = 0, to NWD(a, b) = a. Oznacza to, że jedna z liczb dzieli drugą bez reszty, zatem mniejsza z liczb jest wspólnym dzielnikiem.

Jeśli natomiast r ≠ 0, możemy zapisać, że r = b - xa. Możemy zatem zauważyć, że każda liczba, która dzieli liczby a oraz b, dzieli również całe wyrażenie b - xa, zatem dzieli również r. Wynika z tego to, że NWD liczb a oraz b dzieli również resztę r.

Możemy to zapisać jako NWD(a, b) = NWD(r, a), a ponieważ reszta z dzielenia jest wynikiem operacji modulo, to NWD(a, b) = NWD(b mod a, a).

Słownik