Алгоритм Евклида
Наибольший общий делитель
Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.
Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А × В = НОД(А, В) × НОК(А, В).
|
