Алгоритм евклида программа паскаль

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

Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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 кв кц вывод "НОД=",М кон

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. Выполните на компьютере программу Evkl >

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

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

Приветствуем читателей и посетителей нашего сайта! Сегодня на learnpascal.ru открывается новая рубрика — Алгоритмы. В этой рубрике мы с вами будем разбирать различные алгоритмы, а также их реализацию на Паскале.

Для освоения материала сегодняшнего урока вам понадобится знание циклов и ветвлений.

Сегодня мы рассмотрим три алгоритма(из пяти) на нахождение наибольшего общего делителя двух целых чисел, два из которых непосредственно связывают с именем Евклида. Еще два мы рассмотрим в следующей части.
Наибольший общий делитель (НОД) двух чисел a и b — наибольшее целое число, которое делит их оба.
Пример: НОД(25, 5) = 5; НОД(12, 18) = 6.

Переборный алгоритм

Начинаем перебор с d — наименьшего из двух чисел. Это первый, очевидный кандидат на роль их наибольшего общего делителя. А затем, пока d не делит оба числа, уменьшаем его на единицу. Как только такое деление будет обеспечено, останавливаем уменьшение d.

Обратимся к этой программе, например, с числами 30 и 18. Тогда на пути к ответу(числу 6) ей придется перебрать числа: 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6.

Алгоритм Евклида «с вычитанием»

Пусть a и b — целые числа, тогда верны следующие утверждения:

1. Все общие делители пары a и b являются также общими делителями пары a — b, b;
2. И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b;
3. НОД(A, B) = НОД(A — B, B), если A > B;
4. НОД(A, 0) = A.

1. Если t — произвольный общий делитель a и b, то он делит и разность a — b. Действительно, из a = t * u и b = t * v следует, что a — b = t * u — t * v = t * (u — v). То есть t — также общий делитель а — b и b.
2. Обратно, если t — произвольный делитель общий делитель a — b и b, то он делит и их сумму a — b + b = a. Это можно доказать аналгично предыдущему. Поэтому t — также общий делитель a и b.
3. Делаем вывод, что множество общих делителей a и b совпадает с множеством делителей a — b и b. В частности, совпадают и наибольшие общие делители этих пар.
4. Наибольшее целое, на которое делится число a, есть само число а. Число 0 делится на любое число. Отсюда наибольший общий делитель а и 0 равен а.

Доказанная формула(3) позволяет свести вычисление наибольшего делителя одной пары к вычислению наибольшего общего делителя другой пары, в которой числа уже меньше. Очевидная же формула (4) дает нам понять, когда надо остановиться.

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

Пример. Пусть а = 82 и b = 60. НОД(82, 60) = НОД(22, 60) = НОД(22, 38) = НОД(22, 16) = НОД(6, 16) = НОД(6, 10) = НОД(6, 4) = НОД(2, 4) = НОД(2, 2) = НОД(2, 0) = 2.

На предпоследнем шаге алгоритма, перед появлением 0, оба числа равны, иначе не мог возникнуть 0. Поэтому мы будем извлекать НОД именно в этот момент.

Блок — схема алгоритма Евклида «с вычитанием»

Программа

Алгоритм Евклида с «делением»

Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r).

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

Пример. НОД(82, 60) = НОД(22, 60) = НОД(22, 16) = НОД(6, 16) = НОД(6, 4) = НОД(2, 4) = НОД(0, 2) = 2.

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

Когда говорят «число делиться», то имеют в виду, что оно делиться без остатка. Так A делиться на B, лишь в том случае, если остаток от их деления равен нулю. На этом свойстве основывается понятие наибольшего общего делителя (НОД). НОД двух чисел — это наибольший из всех их общих делителей.

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

Алгоритм Евклида вычитанием.

Найти НОД двух целых чисел немного проще используя операцию вычитания. Для этого потребуется следовать такому условию: если A=B, то НОД найден и он равен одному из чисел, иначе необходимо большее из двух чисел заменить разностью его и меньшего.

Блок-схема Алгоритма Евклида вычитанием:

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

Код программы на C++ (вычитание):

Код программы на Pascal (вычитание):

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

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

Начнем с того, в основе которого лежит операция взятия остатка от деления. Имеем два числа: 112 и 32. Первое больше второго – заменим его остатком от деления 112 на 32. Новая пара чисел включает 16 и 32. Второе больше, поэтому также заменим его остатком от деления 32 на 16, т. е. нулем. В результате получаем НОД=16. Таблично это выглядит так:

А теперь составим с теми же числами таблицу для алгоритма вычитанием.

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

Далее, известно, что в одном случае большее число заменяется разностью его и меньшего числа, а в другом остатком от деления. При делении B на A (большее на меньшее), остаток не может превышать число, стоящее в знаменателе (т. е. A), следовательно, взятие остатка от деления гарантирует оптимальный исход. Но то же самое нельзя сказать в отношении операции вычитания, поскольку совсем необязательно, что сразу после выполнения первого вычитания, B станет меньше или равно A. К примеру, пусть A будет равняться 150, а B – 1100. Так, используя вычитание, мы в первом действии получим B равное 950, в то время как метод деления даст 50.

Блок-схема алгоритма Евклида делением:

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