Версия для печати темы

Автор: kent 22.08.2005 10:44

Всем привет!
Дана задача: Описать нерекурсивную функцию NOD2(A,В) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D.
Никогда не пользовался этим алгоритмом, подскажите в чем суть алгоритма Евклида?

Автор: virt 22.08.2005 12:19

первый вариaнт

function nod(a,b : longint):longint;
begin
   while (a > 0) and (b > 0) do
      if a > b then a := a - b 
         else b := b-a;
   nod := a + b;
end;

второй вариант

function nod(a,b : longint):longint;
begin
   while (a > 0) and (b > 0) do
      if a > b then a := a - b * (a div b )
         else b := b-a * (b div a);
   nod := a + b;
end;

Автор: kent 22.08.2005 12:47

virt, спасибо!!!

Автор: Дож 28.08.2005 14:50

В этих вариантах могут быть кое-какие проблемы если передать отрицательные
числа.

function nod(a,b : longint):longint;
begin
      while (a > 0) and (b > 0) do
         if a > b then a := a - b else b := b-a;
   nod := a + b;
end;
....
BEGIN
....
i:=NOD(-15,-30);
....
END;

i будет равен -45. Что бы этого не случилось нужно делать так:

function nod(a,b : longint):longint;
begin
      If a<0 then a:=abs(a);
      If b<0 then b:=abs(B);
      while (a > 0) and (b > 0) do
         if a > b then a := a - b else b := b-a;
   nod := a + b;
end;
....
BEGIN
....
i:=NOD(-15,-30);
....
END;

Тогда i будет равен 15.

Автор: volvo 28.08.2005 16:31

Дож, а с какой это радости надо передавать в функцию отрицательные числа? В следующий раз внимательно читай задание:Где ты видел отрицательные натуральные числа? Они все положительны ПО ОПРЕДЕЛЕНИЮ !!!

Автор: TarasBer 16.02.2009 14:40

Объясните пожалуйста, зачем делать a := a - b * (a div b ), если есть операция mod?
И вычитать тоже очень неоптимально - возьмите 1000000000 и 1 и найдите их НОД первым алгоритмом.

Автор: volvo 16.02.2009 17:10

TarasBer, ты б еще лет через 10 зашел и попросил объяснить

Автор: amega 16.02.2009 18:30

а че волне вероятно, 4 года терпел, че там еще 4 можна будет