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

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

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

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

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

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

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

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

Постобработка алгоритма Евклида

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

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

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

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

При записи алгоритма Евклида на проедурном языке программирования Паскаль, необходимо строго придерживаться структуры программы. Начать программу недвижимости с заголовком, записать ключевое строе ПРОГРАММЫ и название программы. Пусть программа будет называться ЕВКЛИД. В конце первой строки стоит точка с запятой. Этот знак следует ставить в конце каждой строки программы, а точнее после каждого оператора, процедуры или функции. Его отсутствие приведет к ошибке при отладке программы.

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

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

Var X, Y: целое число;

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

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

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

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

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

читатьln(X);

write(‘Введем второе наврое Y = ‘);

читатьln(Y);

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

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

Для реализации цикла, в котором итерации выполняются по условию, наиболее удобен оператор с условием ПОКА..ДЕЛАТЬ. В решённой задаче эта часть программы будет выглядеть так:

пока X <> Y делаю

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

Описание языка Паскаль записано с хорошим оператором IF..THEN..ELSE.

если X > Y, то X:= X – Y иначе Y:= Y – X;

И по окончании программы на экране отображается желаемый результат.

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

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

программа евклид;

Var X, Y: целое число;

write(‘Начните ввод нового X = ‘);

читатьln(X);

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

читатьln(Y);

пока X <> Y делаю

если X > Y, то X:= X – Y иначе Y:= Y – X;

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

Конец.