8 maja 2021

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 jeszcze pomaga w zrozumieniu rekurencji.

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 rozwiązania, prostsze do zapamiętania. 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 oczywiście 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 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 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ź sobie taką sytuację, że chcesz 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

few hours later

2 | 10 – 2 = 8
2 | 8 – 2 = 6
2 | 6 – 2 = 4
2 | 4 – 2 = 2
2 | 2

Liczenie tego typu operacji ręcznie to byłaby katorga. Dla komputera też nie jest to szczególny luksus, ponieważ w warunkach domowych taka wydajność może jest wystarczająca, ale wyobraź 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.

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ą dodatnie.

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. Wówczas ta druga jest wynikiem operacji NWD.

Generalnie w przypadku nauki algorytmów 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 i już wtedy wiesz o nim wszystko. 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’

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?

To nie jest pytanie retoryczne. To będzie 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ą dodatnie.

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
algorytm Euklidesa python
Algorytm Euklidesa znajduje zastosowanie w języku Python.
Najnowsze wpisy

Jak pomóc dziecku w nauce programowania? Poradnik dla rodziców

Przeczytaj >>

Dlaczego warto uczyć dzieci programowania? – jakie umiejętności rozwija programowanie?

Przeczytaj >>

Python a C++

Przeczytaj >>

Algorytm Euklidesa w języku Python

Przeczytaj >>

10 podstawowych funkcji Excela, które trzeba znać

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Ę KUSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu