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

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

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