Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

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


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

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

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

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).

Викия-сеть

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