Алгоритм Евклида – схема (9 класс, информатика)

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

Алгоритм Евклида – схема (9 класс, информатика)

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

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

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

Алгоритм Евклида – схема (9 класс, информатика)

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

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

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

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

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

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

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

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

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

Алгоритм Евклида – схема (9 класс, информатика)

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

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

Алгоритм Евклида – схема (9 класс, информатика)

Рис. 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.

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

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

Предыдущая
ИнформатикаЯзыки программирования (10 класс, информатика)
Следующая
ИнформатикаСистемы счисления – примеры, таблица, обозначение (9 класс, информатика)
Помогли? Поставьте оценку, пожалуйста.
Плохо
0
Хорошо
0
Супер
0
Спринт-Олимпик.ру