Для иллюстрации основных алгоритмических конструкций в информатике и программировании часто применяют алгоритм Евклида. Применяя этот алгоритм, находят наибольший общий делитель двух целых чисел. Благодаря своей простоте и наглядности этот алгоритм не теряет популярности и по сей день.
Что такое алгоритм Евклида
В математике известен конструктивный алгоритм определения наибольшего общего делителя двух целых чисел, который носит название алгоритма Евклида. Греческий ученый математик Евклид первым описал этот алгоритм в своем научном трактате «Начала».
Евклид жил в третьем веке до нашей эры в древней Греции. Он первым написал трактат по математике, в котором изложил основы планиметрии, стереометрии и теории чисел.
Для понимания сути алгоритма вычисления НОД удобна его геометрическая трактовка.
Рассматриваются два отрезка разной длины. Из большего отрезка вычитают меньший, и затем больший отрезок заменяют результатом проведенного вычитания. Это действие выполняют несколько раз, пока отрезки не станут одинаковой длины. Полученная величина отрезков и есть наибольший общий делитель.
Этапы алгоритма Евклида
Процесс вычисления наибольшего общего делителя двух чисел удобно представить в виде цепочки шагов.
Построчная запись алгоритма Евклида
- Определиться со значением первого числа X.
- Определиться со значением второго числа Y.
- Если X≠Y, то выполнять пункт 4, иначе перейти к пункту 5.
- Если X>Y, то заменить X на X-Y и перейти к пункту 3, иначе заменить Y на Y- X и перейти к пункту 3.
- Считать Х наименьшим общим делителем.
В рассмотренной последовательности используются условные конструкции и конструкция повтора.
Для наглядного представления алгоритма Евклида используется блок-схема.
Запись алгоритма Евклида на языке Паскаль
При записи алгоритма Евклида на процедурном языке программирования Паскаль необходимо строго придерживаться структуры программы. Начинать программу необходимо с заголовка, записывая ключевое слово 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.
Что мы узнали?
Для расчета наибольшего общего делителя двух целых чисел уже более тысячи лет используется простой и наглядный алгоритм, придуманный древнегреческим ученым Евклидом. Он хорошо иллюстрирует работу условных и циклических операторов в языке Паскаль.