Algorytm Euklidesa

31.10.2009 - Damian Rusak
Trudność

Znajdowanie największego wspólnego dzielnika

Wiemy już, że pozostało nam znaleźć sposób na obliczanie największego wspólnego dzielnika.

Wiemy już pewną bardzo ważną rzecz - jeśli jakaś liczba $ d $ dzieli $ a $ i dzieli $ b $, to dzieli również ich różnicę, $ a-b $. W szczególności dotyczy to $ NWD\left(a,b\right) $. Mamy więc:

Jeśli $ a \geq b $ to $ NWD\left(a,b\right) = NWD\left(a-b, b\right) $

Dlaczego? Wiemy już, że jeśli jakaś liczba dzieli $ a $ i $ b $, to dzieli ich różnicę. Więc napewno $ NWD(a,b) \mid a-b $. Z kolei wiemy też, że każdy wspólny dzielnik dwóch liczb dzieli ich sumę, stąd $ NWD(a-b,b) \mid (a-b)+b = a $. Wobec tego zachodzi powyższa równość, bo każdy wspólby dzielnik $ a $ i $ b $ dzieli $ a-b $, i każdy wspólny dzielnik $ a-b $ i $ b $ dzieli $ a $.

Stąd już tylko parę kroków do zachwycającego prostotą algorytmu Euklidesa.

Prześledźmy wykorzystanie faktu $ NWD\left(a,b\right) = NWD\left(a-b, b\right) $ dla konkretnych liczb, na przykład $ 2814 $ i $ 2278 $ :

$ NWD\left(2814,2278\right) = NWD\left(2814 - 2278, 2278\right) = NWD\left(536, 2278\right) = $

$ = NWD\left(2278, 536\right) = NWD\left(2278 - 536, 536\right) = NWD\left(1742, 536\right) = $

$ = NWD\left(1742 - 536, 536\right) = NWD\left(1206, 536\right) = NWD\left(1206 - 563, 563\right) = $

$ = NWD\left(670, 536\right) = NWD\left(670 - 536, 536\right) = NWD\left(134, 536\right) =  $

$  = NWD\left(536, 134\right) = NWD\left(536 - 134, 134\right) = NWD\left(402, 134\right) =  $

$ NWD\left(402 - 134, 134\right) = NWD\left(268, 134\right) = NWD\left(268 - 134, 134\right) =  $

$  = NWD\left(134, 134\right) = NWD\left(134-134, 134\right) = NWD\left(0, 134\right) = 134 $

Uff... trochę to przydługawe, ale w końcu dobrnęliśmy do rozwiązania - $ NWD\left(0, 134\right) $ musi być równe $ 134 $, gdyż $ 0 $ dzieli się przez każdą niezerową liczbę, więc też przez $ 134 $, które z kolei jest największym dzielnikiem $ 134 $, czyż nie?

To, co wykonaliśmy powyżej, to właśnie Algorytm Euklidesa. Dopóki jedna z liczb $ a $ i $ b $ nie jest równa $ 0 $, odejmujemy mniejszą liczbę od większej. Każde kolejne $ NWD $ jest równe poprzedniemu, a kiedyś musimy dobrnąć do zera (dlaczego?) i odnaleźć rozwiązanie, gdyż jeśli $ a \neq 0 $, to $ NWD\left(a, 0\right) = a $.

Jeszcze lepiej

Oczywiście da się ten algorytm ulepszyć. Zauważ, że trochę bez sensu było liczenie kolejno $ NWD\left(2278, 536\right) , NWD\left(1742, 536\right) , NWD\left(1206, 536\right)  $, $ NWD\left(670, 536\right) , NWD\left(134, 536\right) $. Cały czas odejmowaliśmy $ 536 $, aż osiągnęliśmy liczbę mniejszą niż $ 536 $. Tak przecież działa Algorytm Euklidesa - dopóki pierwsza liczba jest większa od drugiej, odejmujemy drugą od pierwszej.

W takim razie nietrudno jest ulepszyć nasz algorytm do takiej postaci:

$ NWD\left(a,b\right) = NWD\left(b, a-\left\lfloor\frac{a}{b}\right\rfloor \cdot b \right) $

Wyjaśnijmy sobie to! $ \left\lfloor\frac{a}{b}\right\rfloor $ to wynik dzielenia $ a $ przez $ b $ bez reszty - mówiąc nieformalnie, jest to ilość pełnych wystąpień $ b $ w $ a $. Innymi słowy, tyle właśnie razy możemy odejmować $ b $ od $ a $, aż dostaniemy liczbę mniejszą od $ b $. W takim razie "kompresujemy" sobie kolejne kroki algorytmu, polegające na żmudnym odejmowaniu $ b $ wielokrotnie, do jedengo kroku. Zauważ, że $ a-\left\lfloor\frac{a}{b}\right\rfloor \cdot b $ to właśnie wynik odjęcia od $ a $ wszystkich "mieszczących" się w $ a $ wystąpień $ b $.

Zauważ, jak przyspiesza to działanie algorytmu - gdybyśmy chcieli poprzednią metodą liczyć $ NWD\left(100000, 1\right) $... Tymczasem w naszej nowej metodzie mamy $ NWD\left(100000, 1\right) = NWD\left(1, 100000 - \left\lfloor \frac{100000}{1}\right\rfloor \cdot 1 \right) = NWD\left(1,0\right) = 1 $.

Zapiszmy nasz algorytm w języku C++:

int NWD(int a, int b){
int q, temp;

while(b){
q = a/b;
temp = b;
b = a - q*b;
a = temp;
}
return a;
}

 

Jest to dokładnie zapis naszego algorytmu - dopóki mniejszy z elementów pary $ (a,b) $ nie jest zerem, wykonujemy "zamianę" $ (a,b) $ na $ (b,a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b\right) $ . Gdy $ b = 0 $, nasz największy wspólny dzielnik to $ a = NWD(a,0) $.

Jak szybko działa ten algorytm? Jeżeli znane są Ci pojęcia złożoności obliczeniowej to zapewne ucieszy Cię wiadomość, że Algorytm Euklidesa działa w czasie logarytmicznym względem wielkości liczb $ a $ i $ b $. Jeśli zaś nie, to zachęcamy do dowiedzenia się czegoś na ten temat - nie mniej jednak oznacza to, że algorytm działa błyskawicznie.

Zachęcamy do zapisania tego algorytmu i wykorzystania go do rozwiązania zadania Monety. Jego dokładna treść i specyfikacja znajdują się na ostatniej stronie artykułu.

4.208335
Twoja ocena: Brak Ocena: 4.2 (24 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com