Algorytm Euklidesa

Ten algorytm jest jednym z najstarszych przepisów - schematów obliczeń. Jest on pomysłowy i szybko daje wynik. Zadaniem jest znalezienie największego wspólnego dzielnika dwóch liczb całkowitych (NWD) - jest to potrzebne na przykład przy skracaniu ułamków. Jak wykonać to zadanie? Pierwszym pomysłem jest sprawdzanie podzielności obu liczb przez kolejne liczby od 2 poczynając, a na mniejszej liczbie kończąc. Można to zrobić na kartce tworząc tabelkę. Przyjrzyjmy się temu sposobowi biorąc liczby 12 i 8:

Lepszym i szybszym rozwiązaniem problemu jest właśnie algorytm Euklidesa. Opiera się on na fakcie, że jeśli od większej liczby odejmiemy mniejszą, to ta mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Gdy przy kolejnym odejmowaniu otrzymamy parę takich samych liczb, to znaleźliśmy NWD.
Oto plan algorytmu:
Najpierw musimy wczytać dwie liczby, których NWD będziemy poszukiwać. Teraz przystępujemy do tworzenia pętli kolejnych odejmowań. Jeśli liczby nie są sobie równe, to musimy zbadać, która jest większa, odjąć od niej mniejszą i zastąpić ją przez otrzymaną różnicę, a następnie wrócić do początku pętli; w przeciwnym wypadku NWD jest np. pierwszą z nich.
Obok widać schemat blokowy a poniżej ślad algorytmu uzyskany w programie ELI:

Poziom    Wynik         Opis
-------------------------------------------------------------------------
 1                       Algorytm Euklidesa - obliczanie NWD dla 
                           dwóch podanych dodatnich liczb całkowitych.
 1         12            Podaj pierwszą liczbę: {całkowita, dodatnia}
 1         8              Podaj drugą liczbę: {całkowita, dodatnia}
 1         Prawda                   a <> b
 1         Prawda                   a > b
 1         4                        a := a - b
 1         Prawda                   a <> b
 1         Fałsz                    a > b
 1         4                        b := b - a
 1         Fałsz                    a <> b
 1         4             NWD wynosi:
 1                       Koniec.

Szybki algorytm Euklidesa polega na braniu reszty z dzielenia większej liczby przez mniejszą zamiast odejmowania. Gdy reszta ta osiągnie zero należy skończyć pętlę i jako wynik wziąć drugą liczbę. Jest on znacznie efektywniejszy od omawianego powyżej. Sprawdźcie to uruchamiając obie wersje algorytmu.