Data aktualizacji: 15 grudnia 2022

Algorytm Euklidesa w języku Python

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,

algorytm Euklidesa c++
Algorytm Euklidesa to podstawowy algorytm, służący do wskazania największego wspólnego dzielnika danych liczb.

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).

Przebieg niezoptymalizowanego algorytmu Euklidesa

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.

algorytm Euklidesa schemat blokowy
Wyliczanie dzielnika algorytmem Euklidesa przydaje się na maturze w zadaniach teoretycznych, jak i praktycznych.

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.

Wersja iteracyjna

def NWD(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Wersja rekurencyjna

def NWD(a, b):
    if a != b:
        if a > b:
            return NWD(a - b, b)
        else:
            return NWD(a, b - a)
    return a

Przebieg zoptymalizowanego algorytmu Euklidesa

Ogó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:

  • Wykonujemy następujące podstawienia:a’ = b
    b’ = a mod b
  • Wykonujemy podstawienia tak długo, dopóki b nie osiągnie wartości 0

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.

Euklides algorytm
Operacja modulo pozwala na dużo efektywniejsze posługiwanie się NWD.

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.

Wersja iteracyjna

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

Wersja rekurencyjna

def NWD(a, b):
    if b != 0:
        return NWD(b, a % b)
    return a

NWW dwóch liczb

Najprostszy sposób na wyliczenie NWW nie wymaga żadnych skomplikowanych algorytmów:

NWW(a,b) = a*b/NWD(a,b)

algorytm Euklidesa python
Algorytm Euklidesa znajduje zastosowanie w języku Python.

Jak oceniasz ten artykuł?

Przykro nam 🙁 , że ten wpis nie był dla Ciebie wystarczająco przydatny!

Będziemy wdzięczni jeżeli napiszesz co moglibyśmy poprawić.

Najnowsze wpisy

Wyszukiwanie Google - wyszukiwanie informacji w Internecie krok po kroku

Przeczytaj >>

Jak sprawdzić komputer przed maturą z informatyki?

Przeczytaj >>

Czy warto zapisać dziecko na programowanie dla przedszkolaków?

Przeczytaj >>

Pierwszy krok ku karierze, czyli jaką wiedzę potrzebuję, aby zacząć pracę w IT jako programista?

Przeczytaj >>

Czy można zostać programistą bez studiów informatycznych?

Przeczytaj >>

JESTEŚ AMBITNY?

Dołącz do nas jeszcze dziś i rozwijaj się w swojej ulubionej dziedzinie we współpracy z nauczycielami, którzy są autorami artykułów na naszym blogu!
POZNAJ OFERTĘ KUrSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu