Сообщений в теме: 2

[Санек]

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.

Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n.

Пример: НОК(16, 20) = 80.

var a,b :longint;
function NOD(x,y:longint):longint; //Функция поиска НОДа двух чисел
  begin
   if x<>0 then NOD:=NOD(y mod x,x)
        else NOD:=y;
  end;
function NOK(x,y:longint):longint; //Функция поиска НОКа двух чисел
  begin
   NOK:=( x div NOD(x,y) ) * y;
  end;
begin
  readln(a, b );
  writeln( 'НОД этих чисел = ', NOD(a,b ) );
  writeln( 'НОК этих чисел = ', NOK(a,b ) );
end.

Сообщение отредактировал Санек: 23 декабря 2011 - 14:16

[АлексейДовгаль]

Хочу добавить более быструю реализацию функции НОД.
Эту реализацию показывал Котов В.М. в Бригантине.

Собственно, время работы данного алгоритма - количество бит в наибольшем числе.

Реализация на С++ (Возможно не самая красивая, ну да не суть)

long NOD(long a, long B)/>
{
        if (a == B)/>
        return a;
        if (a*b == 0)
        return a+b;
        // Если мы уже нашли НОД, то выдаём его значение
        if ((a % 2 == 0) && (b % 2 == 0))
        return 2*NOD(a/2,b/2); // Если оба числа кратны двум, то сокращаем их пополам и выдаём их НОД, домноженный на 2
        if (a % 2 == 0)
        return NOD(a/2,B)/>;
        if (b % 2 == 0)
        return NOD(a,b/2);
        // Если какое-то из двух чисел кратно двум, а другое - нет, то сокращаем его вдвое (ибо эта двойка роли не играет)
        long a1 = a;
        long b1 = b;
        if (a1 < b1)
        swap(a1,b1);
        return NOD((a1-b1)/2,b1); // И самое интересное. Если оба числа нечётные, то мы уменьшаем одно из них (по Евклиду НОД этих чисел от этого не изменится) и сокращаем вдвое.
}

Таким вот образом на каждой итерации отсекается 1 бит.

Результаты вычислений на АСМР (обе реализации на C++):
Евклид:

• 0,037
  
• 0,016
  
• 0,01
  
• 0,009
  
• 0,009
  
• 0,012
  
• 0,01
  
• 0,009
  
• 0,01
  
• 0,01

Котов:

• 0,027
  
• 0,008
  
• 0,008
  
• 0,008
  
• 0,008
  
• 0,008
  
• 0,008
  
• 0,008
  
• 0,01
  
• 0,011