Na maturach z informatyki, zarówno w części teoretycznej, jak i praktycznej, bardzo często pojawia się algorytm Euklidesa. Konieczność wyliczenia największego wspólnego dzielnika (NWD) oraz najmniejszej wspólnej wielokrotności (NWW) mogą również przytrafić się na maturze z matematyki. Nie są to zresztą jedyne powody, dla których warto jest go znać. Algorytm Euklidesa uchodzi za jeden z algorytmów podstawowych. Oznacza to, że jeżeli myślisz o nauce algorytmiki – dobrym pomysłem jest potraktować ten algorytm jako jeden z pierwszych poligonów pod naukę. Takie środowisko testowe daje nam naprawdę wiele możliwości.
Algorytm Euklidesa spotkamy bowiem w dwóch postaciach: niezoptymalizowanej oraz zoptymalizowanej. Oprócz tego każdą z tych postaci możemy zbudować zarówno iteracyjnie, jak i rekurencyjnie. Poznanie jednego algorytmu w kilku wersjach nie dość, że go świetnie utrwala, to dodatkowo ułatwia intuicyjne zrozumienie koncepcji takich jak rekurencja,
Jeżeli uczysz się bezpośrednio „pod maturę” – wówczas rekomenduję nauczenie się wersji niezoptymalizowanej algorytmu Euklidesa. Chodzi o to, że skoro na maturze rzadko jesteśmy oceniani za złożoność obliczeniową algorytmów, warto więc postawić na pewne prostsze do zapamiętania sposoby. Co się tyczy wyboru metody iteracyjnej bądź rekurencyjnej – tutaj kwestia jest już czysto subiektywna i zależy od osobistych preferencji.
Zasadniczym celem algorytmu Euklidesa jest wyliczenie największego wspólnego dzielnika (NWD) dla pary wybranych liczb. Tak wyliczony NWD musi z definicji dzielić wybrane liczby bez reszty i mieć jak największą wartość. Wyliczenie NWD umożliwia też bardzo proste wyliczenie najmniejszej wspólnej wielokrotności (NWW).
Wyobraź sobie, że masz dowolną parę liczb naturalnych większych od zera. Odnalezienie NWD według niezoptymalizowanej wersji algorytmu polega na tym, aby odejmować mniejszą liczbę od większej tak długo, aż obie odejmowane liczby z pary nie będą sobie równe. Wygląda to następująco:
NWD(24, 20) = ?
- stwierdzamy, że 20 jest mniejsze niż 24
24 | 20
24 – 20 = 4 | 20
4 | 20
NWD(4, 20) = ?
- stwierdzamy, że 4 jest mniejsze niż 20
4 | 20
4 | 20 – 4 = 16
4 | 16
NWD(4, 16) = ?
- stwierdzamy, że 4 jest mniejsze niż 16
4 | 16
4 | 16 – 4 = 12
4 | 12
NWD(4, 12) = ?
- stwierdzamy, że 4 jest mniejsze niż 12
4 | 12
4 | 12 – 4 = 8
4 | 8
NWD(4, 8) = ?
- stwierdzamy, że 4 jest mniejsze niż 8
4 | 8
4 | 8 – 4 = 4
4 | 4
NWD(4, 4) = ?
- stwierdzamy, że 4 oczywiście jest równe 4, więc dowolna liczba z powyższej pary jest jednocześnie wynikiem
NWD(4, 4) = 4, więc NWD(24, 20) = 4
Skoro wyliczenie NWD jest kwestią powtarzania zwyczajnych operacji odejmowania, w jakim celu mielibyśmy doszukiwać się innej metody? Niestety czasem proste metody mają swoje wady. Otóż wyobraźmy sobie sytuację, w której chcemy obliczyć NWD z takich liczb jak zawarte w przykładzie poniżej:
NWD(2, 200 000) = ?
2 | 200 000 – 2 = 199 998
2 | 199 998 – 2 = 199 996
2 | 199 996 – 2 = 199 994
2 | 199 994 – 2 = 199 992
2 | 199 992 – 2 = 199 900
…
wiele, wiele obliczeń później
…
2 | 10 – 2 = 8
2 | 8 – 2 = 6
2 | 6 – 2 = 4
2 | 4 – 2 = 2
2 | 2
Liczenie tego typu operacji ręcznie byłoby katorgą. Dla komputera też nie jest to szczególny luksus; w warunkach domowych taka wydajność może jest wystarczająca, ale wyobraźmy sobie wykorzystywanie tak nieoptymalnego algorytmu na serwerach zaawansowanego kalkulatora matematycznego Wolfram Alpha. To istna strata prądu, możliwości obliczeniowych i zwyczajnie czasu.
Niemniej na maturze jest to rozwiązanie w zupełności wystarczające. Poniżej znajdziesz implementację algorytmu w Pythonie zarówno w wersji iteracyjnej, jak i rekurencyjnej. Zakładamy, że zarówno a, jak i b są dodatnimi liczbami całkowitymi.
def NWD(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return adef NWD(a, b):
if a != b:
if a > b:
return NWD(a - b, b)
else:
return NWD(a, b - a)
return aOgólna metodyka działania zoptymalizowanej wersji algorytmu nie różni się aż tak wiele, gdyż również opiera się na podstawianiu nowych (mniejszych) liczb w parze, dopóki nie ujrzymy warunku granicznego. Nie wykorzystujemy jednak do tego odejmowania. Operacja modulo (reszty z dzielenia) pozwala na o wiele efektywniejsze podstawianie kolejnych liczb, zaś warunkiem granicznym jest moment, w którym jedna z tych liczb będzie równa 0 - nie czekamy więc, aż liczby się zrównają. Wówczas ta druga, niezerowa jest wynikiem operacji NWD.
Generalnie w przypadku nauki algorytmów początkowo nie warto jest przesadnie długo głowić się nad opisami czy bardziej pogmatwaną teorią. Najlepiej jest po prostu zobaczyć, jak dany algorytm działa, później zajrzeć do kodu; wtedy wszystko sie wyjaśnia. Dlatego od razu przejdźmy do przykładu.
Nasze działania dla wyliczenia NWD(a, b) będą wyglądały tak:
Tak to wygląda na przykładzie:
NWD(24, 20) = ?
a’ = 20
b’ = 4
NWD(20, 4) = ?
a’ = 4
b’ = 0
NWD(24, 20) = a’
Możemy zatem stwierdzić, że:
NWD(24, 20) = 4
Jest to rozwiązanie o wiele efektywniejsze aniżeli poprzednio zaprezentowana wersja z odejmowaniem. Pomyśl: ile przebiegów algorytmu musiałoby zostać wykonanych, aby wyliczyć NWD dla liczb: 1 000 000 oraz 1 z użyciem algorytmu Euklidesa w wersji zoptymalizowanej, a ile w niezoptymalizowanej?
Różnica jest, jak można się domyslić, ogromna. Dokładnie 1 przebieg dla wersji zoptymalizowanej oraz 999 999 przebiegów dla wersji niezoptymalizowanej. Dlatego warto znać zoptymalizowaną wersję algorytmu Euklidesa.
Poniżej znajdziesz implementację algorytmu w Pythonie zarówno w wersji iteracyjnej, jak i rekurencyjnej. Zakładamy, że zarówno a, jak i b są dodatnimi liczbami całkowitymi.
def NWD(a, b):
while b != 0:
temp = b
b = a % b
a = temp
return adef NWD(a, b):
if b != 0:
return NWD(b, a % b)
return aNajprostszy sposób na wyliczenie NWW nie wymaga żadnych skomplikowanych algorytmów:
NWW(a,b) = a*b/NWD(a,b)
