Презентация на тему: Алгоритм Евклида

Алгоритм Евклида Составила: Антонова Е.П.2009г.

Постановка ЗадачиРассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:НОД(12,18) = 6.Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:Дано: М, N Найти: НОД(М,N).

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

Идея алгоритмаИдея этого алгоритма основана на том свойстве, что если M>N, тоНОД(М,N) = НОД(М - N,N).Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.

ДоказательствоПусть К — общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п — натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности M-N, в том числе и наибольший общий делитель. Отсюда:НОД(М,N) = НОД(М - N,N).Второе очевидное свойство:НОД(М,М) = М.

Алгоритм Евклидаесли числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;заменить большее число разностью большего и меньшего из чисел;вернуться к выполнению п. 1.

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

Задание для практики:Напишите программу, реализующую алгоритм Евклида для нахождения наибольшего общего делителя для двух натуральных чисел

Программа на языке ПаскальProgram Evklid; var М, N : integer; beginwriteln('Введите M и N'); readln(M,N); while MN do beginif M>N then M:=M-N else N:=N-Mend;write('HOD=',M) end.