Наибольший общий делитель, Алгоритм Евклида Опции

[kent]

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

Сообщение отредактировано: kent - 22.08.2005 10:46

[virt]

первый вари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]

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

[Дож]

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

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:34

[volvo]

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

Дож, а с какой это радости надо передавать в функцию отрицательные числа? В следующий раз внимательно читай задание:

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

Где ты видел отрицательные натуральные числа? Они все положительны ПО ОПРЕДЕЛЕНИЮ !!!

[TarasBer]

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

[volvo]

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

[amega]

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