Примеры реализации алгоритма Евклида

Материал из Викиучебника

Далее приводятся реализации алгоритма Евклида для вычисления НОД на различных языках программирования.

[править] Scheme

Алгоритм вычитанием

(define gcd (lambda (a b)
  (if (> a b) (gcd (- a b) b)
     (if (< a b) (gcd a (- b a))
        a))))

[править] Ruby

Функция в рекурсивном виде:

def gcd(a, b)
    return a if b.eql? 0
    gcd(b, a % b)
end

Функция в нерекурсивном виде:

def gcd(a, b)
    while !b.eql? 0
        a, b = b, a % b
    end
    return a
end

Алгоритм вычитанием:

def gcd(a, b)
    while !a.eql? b
        if a > b
            a -= b
        else
           b -= a
        end
    end
    return a
end

[править] Python

Функция в рекурсивном виде:

def gcd(a, b):
  if b == 0: return a
  else: return gcd(b, a % b)

Функция в нерекурсивном виде:

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

[править] Си

int gcd(int a, int b) {
  int c;
  while (b) {
     c = a % b;
     a = b;
     b = c;        
  }
  return abs(a);
}

Более короткое решение:

int gcd(int a, int b) {
 while(b) b^=a^=b^=a%=b;
 return a;
}

Та же функция в рекурсивном виде:

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

Немного короче:

int gcd(int a, int b) {
  return (b == 0)?a:gcd(b, a % b);
}

Алгоритм вычитанием:

 int gcd(int a, int b) {
  while ( a != b) {
     if (a > b) a -= b;
      else b -= a;
  }
 return a;
}

[править] Форт (диалект RetroForth)

Рекурсивный алгоритм

: НОД  ( n1 n2 -- n )  tuck mod 0; НОД ;

[править] Haskell

gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД от 0 и 0 не определён."
gcd x y = gcd' (abs x) (abs y)
  where gcd' x 0 = x
        gcd' x y = gcd' y (rem x y)

[править] Глагол

 ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; 
 УКАЗ 
   ПОКА (a # 0) И (b # 0) ВЫП 
     ЕСЛИ a >= b ТО 
       a := a ОСТАТОК b 
     ИНАЧЕ 
       b := b ОСТАТОК a 
     КОН 
   КОН; 
   ВОЗВРАТ a + b 
 КОН НОД;

[править] Pascal

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

В рекурсивном виде:

  function nod(var a, b: longint): longint; 
  begin
   if (a = 0) or (b = 0) then
     if a = 0 then
       nod:= b
     else 
       nod:= a
   else 
     if a >= b then 
       nod:= nod( a mod b, b)
     else 
       nod:= nod( a, b mod a)
  end;

[править] Prolog

 ?GCD(a,b,x)
 
 GCD(0,b,b) <- 
 GCD(a,0,a) <-
 GCD(a,b,x) <- a >= b, m is a mod b, GCD(m, b, x)
 GCD(a,b,x) <- a < b, m is b mod a, GCD(a, m, x)

[править] SWI-Prolog

gcd(0,B,B).
gcd(A,0,A).

gcd(A,B,X) :-  A >= B, M is A mod B, gcd(M, B, X). 
gcd(A,B,X) :-  A < B, M is B mod A, gcd(A, M, X).