Алгоритм Евклида для нахождения наибольшего общего делителя

Алгоритм Евклида служит для нахождения наибольшего общего делителя двух чисел. 

На входные числа накладываются определенные ограничения, а именно числа должны быть не равные нулю, целые и неотрицательные. 

Рассмотрим реализацию алгоритма Евклида по шагам:

Шаг 1. Задать числа X, Y. 

Шаг 2. Присвоить X переменной A, Y переменной B. 

Шаг 3. Пока А не равно В, выполнить 

если А больше В, то присвоить А минус B переменной А 

иначе присвоить В минус А переменной В. 

Шаг 4. Присвоить переменной D значение переменной А. 

Шаг 5. Конец. 

Алгоритм в виде блок-схемы выглядит так:

 

Рис 1.

Рассмотрим конкретное задание, например: 

Найти наибольший общий делитель двух чисел 48 и 18.

Решим эту задачу установкой контрольной точки. На рис 1. контрольная точка обозначена чёрным треугольником. Контрольную точку устанавливают на выбранной пользователем строке алгоритма. Выполнение алгоритма продолжается до контрольной точки и  приостанавливается на отмеченной строке. В трассировочную таблицу записываются текущие значения переменных и выражений. Если значение переменной не изменилось, его можно не вносить в таблицу. При необходимости можно поставить несколько контрольных точек.

Трассировочная таблица будет иметь следующий вид:

Рис 2.

Таким образом наибольший общий делитель двух чисел 48 и 18 будет 6.