Пример алгоритма

Написано: четверг, 28 января 2016 г. автор Dmitry Volk
0

В качестве примера можно привести алгоритм Евклида.
Алгоритм Евклида — эффективный метод вычисления наибольшего общего делителя (НОД). Назван в честь греческого математика Евклида; один из древнейших алгоритмов, который используют до сих пор.
Описан в «Началах» Евклида (примерно 300 до н. э.), а именно в книгах VII и X. В седьмой книге описан алгоритм для целых чисел, а в десятой — для длин отрезков.
Существует несколько вариантов алгоритма, ниже записанный в псевдокоде рекурсивный вариант:
функция нод(a, b)
    если b = 0
       возврат a
    иначе
       возврат нод(b, a mod b)

НОД чисел 1599 и 650:




Шаг 11599 = 650*2 + 299


Шаг 2650 = 299*2 + 52


Шаг 3299 = 52*5 + 39


Шаг 452 = 39*1 + 13


Шаг 539 = 13*3 + 0












Иллюстрация выполнения алгоритма Евклида для вычисления НОД чисел 1599 и 650.