Algorytm euklidesa

Algorytm Euklidesa to algorytm, który jest jednym z pierwszych analizowanych, a następnie implementowanych na lekcjach informatyki, na których wprowadzane jest programowanie. Algorytm Euklidesa pozwala na wyznaczenie największego wspólnego dzielnika dla dwóch liczb całkowitych.
Najpierw rozwinę zagadnienie największego wspólnego dzielnika, zapisujemy skrótem NWD. Jeżeli mamy dane dwie liczby całkowite a oraz b, to NWD to największa liczba całkowita, która jest dzielnikiem liczb a oraz b. Oczywiście dzielenie musi odbyć się bez reszty.
Przykład:
12 oraz 6.
Dzielniki liczby 12 to: 1, 2, 3, 4, 6.
Dzielniki liczby 6 to: 1, 2, 3, 6.
NWD(12, 6) to 6.

Algorytm Euklidesa można przedstawić za pomocą schematu blokowego.

Wytłumaczę teraz jak zbudowane są schematy blokowe.
W każdym schemacie blokowym musi występować blok START oraz STOP.
Blok START to miejsce, gdzie zaczynamy nasz algorytm.
Następnie równoległoboki to bloki wejścia oraz wyjścia. Za ich pomocą wczytujemy dane od użytkownika oraz wypisujemy je użytkownikowi.
Romb to blok decyzyjny lub warunkowy. Jak sama nazwa sugeruje, znajduje się w nim warunek. W bloku warunkowym musi być warunek, na który można odpowiedzieć TAK lub NIE. Przykłady: czy liczba a jest parzysta? Nie może być „jaka liczba jest parzysta”.
Jeżeli mamy kilka bloków decyzyjnych, to dobrą praktyką jest jednolite umieszczanie tak oraz nie. W naszym przypadku we wszystkich blokach decyzyjnych po prawej stronie mamy nie, po lewej tak.
Następnie prostokąt to blok operacyjny, w którym wykonujemy działania na zmiennych.
Blok STOP kończy algorytm.

Wytłumaczę krok po kroku, jak odczytać nasz schemat blokowy.
START
Użytkownik wprowadza liczbę a.
Użytkownik wprowadza liczbę b.
Sprawdzany jest warunek, czy liczba a jest różna niż liczba b. Jeżeli liczby nie są różne, czyli jeżeli liczby są takie same, to wypisujemy zmienną a oraz kończymy algorytm.
Jeżeli liczby są różne, to dalej jest kolejny blok warunkowy, który sprawdza, czy liczba a jest większa niż b. Jeżeli nie, to b staje się b – a. Jeżeli a jest większa niż b, to a staje się a – b.
Dalej wracamy przed pierwszy blok warunkowy i powtarzamy algorytm.

Przeanalizujemy teraz ten sam algorytm na konkretnych przykładach.
Weźmy jako przykład 3 oraz 9.
Wprowadzamy do algorytmu a=3 oraz b=9.
Czy liczby są różne? Tak.
Czy a jest większe niż b? Nie, ab:=b-a
b:=9-3=6
W tym momencie nasze a = 3, a nasze b = 6.
Czy liczby są różne? Tak.
Czy a jest większe niż b? Nie, bo ab:=6-3=3
W tym momencie nasze a = 3, a nasze b = 3
Czy liczby są różne? Nie, bo 3 = 3
Wypisana zostaje wartość 3. Więc NWD(9,3) to 3 i jest to prawda, także nasz algorytm działa.

Kolejnym przykładem niech będzie 2 oraz 13.
Wprowadzamy więc do algorytmu a = 2 oraz b = 13.
Czy liczby są różne? Tak.
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
Dlatego:
b: = b-a
b: = 13-2=11
W tym momencie nasze a = 2, a nasze b = 11.
Czy liczby są różne? Tak.
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
Dlatego:
b: = b-a
b: = 11 – 2 = 9
W tym momencie nasze a = 2, a nasze b = 9.
Czy liczby są różne? Tak
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
b: = b-a
b: = 9 – 2 =7
W tym momencie nasze a = 2, a nasze b = 7.
Czy liczby są różne? Tak
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
b: = b-a
b: = 7 – 2 =5
W tym momencie nasze a = 2, a nasze b = 5.
Czy liczby są różne? Tak
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
b: = b-a
b: = 5 – 2 = 3
W tym momencie nasze a = 2, a nasze b = 3.
Czy liczby są różne? Tak
Czy a jest większe niż b? Nie, ponieważ a jest mniejsze niż b.
b: = b-a
b: = 3 – 2 = 1
W tym momencie nasze a = 2, a nasze b = 1.
Czy liczby są różne? Tak
Czy a jest większe niż b? Tak.
a: = a – b
a: = 2 – 1 = 1
W tym momencie nasze a = 1, a nasze b = 1.
Czy liczby są różne? Nie
Zostaje wypisane 1.
Koniec algorytmu.

Zaimplementuję teraz algorytm Euklidesa w języku programowania python. Moim zdaniem python to jeden z prostszych języków programowania, jest bardzo intuicyjny.

a = 10
b = 15
print(„NWD(%s, %s) „% (a, b))
while a!=b:
if a>b:
a=a-b
else:
b=b-a

print(„wynosi %s” %a)

Wytłumaczę teraz powyższy kod. Najpierw ustalam zmienne a oraz b. Ja robię to „od razu”, ale można łatwo przerobić ten program, aby pobierał zmienne od użytkownika. Następnie wypisuję od razu, że NWD(a, b). Dlaczego robię to przed całym kodem? Dlatego, że zmienne w trakcie wykonywania programu się zmienią. Nie ma potrzeby ustalania zmiennych pomocniczych, które będą pamiętać wprowadzone zmienne. Dalej przechodzimy do pętli while. Wykonuje się ona dopóki a jest różne niż b, inaczej a nie jest równe b. W tej pętli wykonuje się instrukcja warunkowa. Jest ona dokładnie taka, jak w schemacie blokowym i już wytłumaczyłam działanie tej instrukcji. Jeżeli a będzie równe b kończy się pętla, zostaje nam wypisany największy wspólny dzielnik.
W wyniku otrzymujemy:

Mój kod można skopiować, wkleić do dowolnego kompilatora online języka python oraz dowolnie go modyfikować. Jeżeli chcecie przetestować inne liczby wystarczy zamiast a = 10 oraz b = 15 podstawić inne liczby.
Należy pamiętać, że python jest językiem bardzo czułym na wcięcia. Jeżeli przez przypadek je usuniecie, to program nie będzie działać poprawnie.