Наибольший общий делитель (НОД) (Greatest Common Divisor - GCD) двух
чисел - это наибольшее целое число, на которое делятся два числа без остатка.
Например, НОД чисел 12 и 9 равен 3, потому что 3 - наибольшее целое число, на
которое 12 и 9 делятся без остатка. Два числа являются взаимно простыми (relatively
prime), если их наибольший общий делитель равен 1.
Математик Эйлер (восемнадцатый век) обнаружил интересный факт:
Если В делится на А нацело, то НОД(А, В) = А.
В противном случае НОД(А, В) = НОД(В mod А, А).
Это положение можно использовать для быстрого вычисления наибольшего
общего делителя. Например:
НОД(9, 12) = НОД(12 mod 9, 9) = НОД(3, 9) = 3
На каждом шаге сравниваемые числа уменьшаются, потому что 1 < В mod A < A,
если А не делится на В нацело. Если параметры продолжают уменьшаться, то А в ко-
нечном счете достигает значения 1. Поскольку на 1 делится нацело любое число В,
рекурсия завершается.
Открытие Эйлера привело к достаточно простому рекурсивному алгоритму
для вычисления НОД:
function Gcd(A, В : Longint) : Longint;
begin
if (В mod A)=0 then // Если А делит В нацело, то значение вычислено.
Gcd := A
else // В противном случае функция вычисляется
// рекурсивно.
Gcd := Gcd(B mod A,A);
end;
|
Главная
Каталог файлов
