Алгоритм евклида сообщение по информатике

Обновлено: 30.06.2024

Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

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

Идея этого алгоритма основана на том свойстве, что если M>N, то

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Легко доказать это свойство. Пусть К - общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.

Второе очевидное свойство:

Для "ручного" счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;

2) заменить большее число разностью большего и меньшего из чисел;

3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М=32, N=24:

Получили: НОД(32, 24) =НОД(8, 8) = 8, что верно.

Описание алгоритма Евклида блок-схемой

На рис. 3.12 приведена блок-схема алгоритма Евклида.

Рис. 3.12. Блок-схема алгоритма Евклида

Структура алгоритма - цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.

Шаг	Операция	M	N	Условие
1	ввод М	32
2	ввод N	24
3	M ¹ N	32 ¹ 24, да
4	M>N	32>24, да
5	M:=M-N	8
6	M ¹ N	8 ¹ 24, да
7	M>N	8>24, нет
8	N:=N-M	16
9	M ¹ N	8 ¹ 16, да
10	M>N	8>16, нет
11	N:=N-M	8
12	M ¹ N	8 ¹ 8, нет
13	вывод M	8
14	конец

В итоге получился верный результат.

Программа на АЯ и на Паскале

Запишем алгоритм на АЯ и программу на Паскале.

алг Евклид
цел М, N
нач
вывод " Введите М и N" ввод М, N
пока М N, повторять
нц
если M>N
то M:=M-N
иначе N:=N-M
кв
кц
вывод "НОД 300">Program Evklid;
var M, N: integer;
begin
writeln('Введите М и N');
readln(M, N);
while M<>N do
begin
if M>N
then M:=M-N
else N:=N-M
end;
write('Н0Д=',М)
end.

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.

2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

Алгоритм Евклида- это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Вложение	Размер
algoritm_evklida.pptx	274.93 КБ
konspekt.docx	56.55 КБ

Предварительный просмотр:

Подписи к слайдам:

АЛГОРИТМ ЕВКЛИДА ЕВКЛИД , древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд "Начала" (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов. Оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки. Евклид (365-300 до. н. э.)

Вычисление НОД НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. НОД( a , b )= НОД( a-b, b )= НОД( a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД ( 18 , 45 ) = НОД ( 18 , 45-18 ) = НОД ( 18 , 27 ) = НОД (18 , 9 ) = =НОД(9,9)=9 Пример :

ШАГ Операция M N Условие 1 Ввод M 48 2 Ввод N 18 3 M  N 48 18, да 4 M>N 48>18, да 5 M:=M-N 30 6 M  N 30  18, да 7 M>N 30 >18, да 8 M:=M-N 12 9 M  N 12 18, да 10 M>N 12 >18, нет 11 N:=N-M 6 12 M  N 12  6, да 13 M>N 12 >6, да 14 M:=M-N 6 15 M  N 6  6, нет 16 Вывод M

program Evklid ; var m, n: integer; begin writeln (' vved 2 chisla '); readln ( m,n ); while m<>n do begin if m>n then m:=m-n else n := n-m ; end; write ('nod=',m); readln end.

0.Выполните на компьютере программу Evklid . Протестируйте её при значениях М=32, N=24; M=696, N=234. 1 . Проверить, являются ли два данных числа взаимно простыми. Примечание. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. 2 . Найти наименьшее общее кратное (НОК) чисел n и m , если НОК( n , m ) = n * m / НОД ( n , m ). 3 . Даны натуральные числа m и n . Найти такие натуральные p и q , не имеющие общих делителей, что p / q = m / n . 4. Найти НОД трех чисел. Примечание . НОД( a , b , c )= НОД(НОД( a , b ), c ) Задачи

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

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

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

Рис. 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. В конце программы обязательно ставится точка.

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

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

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

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

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

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

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

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

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

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

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

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

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

Var X, Y : integer;

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

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

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

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

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

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

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

Постановка задачи: Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел

Алгоритм нахождения НОД Разложить числа на простые множители. Найти общие множители. Найти их произведение.

Алгоритм Евклида Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма. Заменить большее число разностью большего и меньшего из чисел. Вернуться к выполнению п. 1.

Читайте также: