Слайд 1Алгоритм Евклида
Составила: Антонова Е.П.
2009г.
Слайд 2Постановка Задачи
Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего
делителя (НОД) двух натуральных чисел.
Вспомним математику. Наибольший общий делитель двух
натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
НОД(12,18) = 6.
Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:
Дано: М, N
Найти: НОД(М,N).
Слайд 3Решение
Не существует формулы для нахождения НОД двух чисел. Но зато
достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ
решения этой задачи.
Называется он алгоритмом Евклида.
Слайд 4Идея алгоритма
Идея этого алгоритма основана на том свойстве, что если
M>N, то
НОД(М,N) = НОД(М - N,N).
Иначе говоря, НОД двух натуральных
чисел равен НОД их положительной разности и меньшего числа.
Слайд 5Доказательство
Пусть К — общий делитель М и. N (M>N). Это
значит, что М = тК, N = пК, где т,
п — натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности M-N, в том числе и наибольший общий делитель. Отсюда:
НОД(М,N) = НОД(М - N,N).
Второе очевидное свойство:
НОД(М,М) = М.
Слайд 6Алгоритм Евклида
если числа равны, то взять любое из них в
качестве ответа, в противном случае продолжить выполнение алгоритма;
заменить большее число
разностью большего и меньшего из чисел;
вернуться к выполнению п. 1.
Слайд 7Блок-схема алгоритма Евклида
Слайд 8Задание для практики:
Напишите программу, реализующую алгоритм Евклида для нахождения наибольшего
общего делителя для двух натуральных чисел
Слайд 9Программа на языке Паскаль
Program Evklid;
var М, N : integer;
begin
writeln('Введите M и N');
readln(M,N);
while MN do
begin
if M>N
then M:=M-N else N:=N-M
end;
write('HOD=',M)
end.
