Фэндом

Математика

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

1458статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

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

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;

Более простая рекурсивная реализация:

 function gcd(a,b:integer):integer;
 begin
 if a*b=0 
 then nod:=a+b
 else nod:=nod(b, a mod b);
 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).

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на Фэндоме

Случайная вики