Алгоритм Евклида Составила: Антонова Е.П. 2009г.. - презентация

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.