Алгоритм Евклида
Наибольший общий делительРассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел. Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так: НОД(12, 18) = 6. Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М, N). В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида. Идея алгоритма ЕвклидаИдея этого алгоритма основана на том свойстве, что если M>N, то НОД(М, N) = НОД(М - N, 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. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234. 2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу: НОД(А, B, С) = НОД(НОД(А, В), С). 3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А × В = НОД(А, В) × НОК(А, В).
| 
