Algorytmika

Algorytm - Precyzyjny opis sposobu rozwiązania określonego zadania lub osiągnięcia jakiegoś celu.

                          Struktura liniowa                             Rozgałęzienie warunkowe

                                                  Pętla - interacja powtórznie

algorytm Euklidesa (ang. Euclid algorithm)

Algorytm wyznaczania największego dzielnika dwóch liczb całkowitych. Został on podany przez matematyka greckiego Euklidesa (ok. 365 -- ok. 300 p.n.e.) w jego fundamentalnym dziele Elementy. Uznawany za pierwszy algorytm, chociaż na terenach obecnych Chin i Indii znane były wcześniej inne przepisy na wykonywanie obliczeń. Do czasów ery komputerowej, a więc do połowy XX wieku, algorytm Euklidesa uchodził za synonim algorytmu.

Dla dwóch danych liczb a i b, algorytm Euklidesa polega na wielokrotnym zastępowaniu większej z nich przez resztę z dzielenia większej liczby przez mniejszą, aż jedna z nich osiąga wartość 0, wtedy ta druga jest największym wspólnym dzielnikiem danych liczb.      Na przykład dla liczb 36 i 15 otrzymujemy ciąg par: (36, 15), (6, 15), (6, 3), (0, 3). A zatem 3 jest największym wspólnym dzielnikiem liczb 36 i 15.