Алгоритм Евклида Составила: Антонова Е.П. 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; 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.