Обсуждение:Реализации алгоритмов/Алгоритм Евклида

Реализации на Паскале

Ничего не могу сказать про реализации алгоритма на прочих языках, но вот на Pascal'е они ужасны. Зачем

• столько сравнений с нулем,
• передача параметров по ссылке,
• куча Exit'ов в бинарном алгоритме,
• операции Trunc при работе с целыми числами?

Это же классическая задача, всё решается намного проще:

  function GCD(a, b: longint): longint; 
  begin
    if (b = 0) then
      result := abs(a) // с модулем чуть корректнее
    else 
      result := GCD(b, a mod b);
  end;

  function GCD(a, b: integer): integer;
  begin
    if (a = 0) then Result := b else
    if (b = 0) or (a = b) then Result := a else
    if (a = 1) or (b = 1) then Result := 1 else
    if (a mod 2 = 0) and (b mod 2 = 0)  then Result := 2*GCD(a div 2, b div 2) else
    if (a mod 2 = 0) and (b mod 2 <> 0) then Result := GCD(a div 2, b) else
    if (a mod 2 <> 0) and (b mod 2 = 0) then Result := GCD(a, b div 2) else
      Result:= GCD(b, Abs(a - b));
  end;

Bosik GN 17:16, 21 июня 2010 (UTC)

== НОД(a, b) = НОД(a, a − b) при a ≥ b - это ошибка