Алгоритм Евклида

4.6

Средняя оценка: 4.6

Всего получено оценок: 237.

Для иллюстрации основных алгоритмических конструкций в информатике и программировании часто применяют алгоритм Евклида. Применяя этот алгоритм, находят наибольший общий делитель двух целых чисел. Благодаря своей простоте и наглядности этот алгоритм не теряет популярности и по сей день.

Что такое алгоритм Евклида

В математике известен конструктивный алгоритм определения наибольшего общего делителя двух целых чисел, который носит название алгоритма Евклида. Греческий ученый математик Евклид первым описал этот алгоритм в своем научном трактате «Начала».

Евклид жил в третьем веке до нашей эры в древней Греции. Он первым написал трактат по математике, в котором изложил основы планиметрии, стереометрии и теории чисел.

Рис. 1. Портрет древнегреческого математика Евклида.

Для понимания сути алгоритма вычисления НОД удобна его геометрическая трактовка.

Рассматриваются два отрезка разной длины. Из большего отрезка вычитают меньший, и затем больший отрезок заменяют результатом проведенного вычитания. Это действие выполняют несколько раз, пока отрезки не станут одинаковой длины. Полученная величина отрезков и есть наибольший общий делитель.

Этапы алгоритма Евклида

Процесс вычисления наибольшего общего делителя двух чисел удобно представить в виде цепочки шагов.

Построчная запись алгоритма Евклида

Определиться со значением первого числа X.
Определиться со значением второго числа Y.
Если X≠Y, то выполнять пункт 4, иначе перейти к пункту 5.
Если X>Y, то заменить X на X-Y и перейти к пункту 3, иначе заменить Y на Y- X и перейти к пункту 3.
Считать Х наименьшим общим делителем.

В рассмотренной последовательности используются условные конструкции и конструкция повтора.

Для наглядного представления алгоритма Евклида используется блок-схема.

Рис. 2. Блок схема нахождения НОД по алгоритму Евклида.

Запись алгоритма Евклида на языке Паскаль

Рис. 3. Логотип интегрированной среды разработки TurboPascal.

При записи алгоритма Евклида на процедурном языке программирования Паскаль необходимо строго придерживаться структуры программы. Начинать программу необходимо с заголовка, записывая ключевое слово PROGRAM и название программы. Пусть программа называется EVKLID. В конце первой строки ставится точка с запятой. Этот знак следует ставить в конце каждой строки программы, а точнее после каждого оператора, процедуры или функции. Отсутствие его приведет к ошибке при отладке программы.

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

Описание переменных

В алгоритме используется всего две переменные X и Y, которые следует описать в разделе описания переменных, задавая им целый тип.

Var X, Y : integer;

Основная часть программы, в которой производятся все вычисления, заключается в операторные скобки begin и end. В конце программы обязательно ставится точка.

Ввод переменных с клавиатуры

Значения переменных X и Y удобнее всего вводить с клавиатуры, используя процедуры ввода чисел с клавиатуры READLN. Перед вводом данных лучше вывести пользователю будущей программы сообщение «Введите число» с использованием процедуры вывода WRITELN.

Часть программы, предназначенная для ввода чисел, может выглядеть так:

write(‘Введите первое число X = ‘);

readln(X);

write(‘Введите второе число Y = ‘);

readln(Y);

Организация повтора

Операцию вычитания в соответствии с алгоритмом следует выполнять до тех пор, пока выполняется условие неравности переменных X и Y. При равенстве X и Y повтор следует прекратить. Искомое число найдено.

Для реализации цикла, в котором итерации выполняются в соответствии с условием, удобнее всего использовать оператор с предусловием WHILE..DO. В решаемой задаче эта часть программы будет выглядеть так:

while X <> Y do

Запись условной конструкции на языке Паскаль

Условие на языке Паскаль записывается с помощью оператора IF..THEN..ELSE.

if X > Y then X:= X – Y else Y:= Y – X;

И в завершении программы, искомый результат выводится на экран.

Writeln (‘НОД чисел X и Y равен ‘, X);

Весь текст программы будет иметь вид:

program evklid;

Var X, Y : integer;

write(‘Начните вводить первое число X = ‘);

readln(X);

write(‘Начните вводить второе число Y = ‘);

readln(Y);

while X <> Y do

if X > Y then X:= X – Y else Y:= Y – X;

Writeln (‘НОД чисел X и Y равен ‘, X);

End.

Что мы узнали?

Для расчета наибольшего общего делителя двух целых чисел уже более тысячи лет используется простой и наглядный алгоритм, придуманный древнегреческим ученым Евклидом. Он хорошо иллюстрирует работу условных и циклических операторов в языке Паскаль.