Реализации алгоритмов/Алгоритм Евклида: различия между версиями
Содержимое удалено Содержимое добавлено
Freidom (обсуждение | вклад) |
GeStat (обсуждение | вклад) Нет описания правки |
||
Строка 243: | Строка 243: | ||
return a; |
return a; |
||
} |
} |
||
</source> |
|||
== [[MapBasic]] == |
|||
<source lang="csharp"> |
|||
Function NOD(a As Integer, b As Integer) As Integer |
|||
Dim d As Integer |
|||
Do While a <> 0 and b <> 0 |
|||
If a >=b Then |
|||
a = a mod b |
|||
Else |
|||
b = b mod a |
|||
End If |
|||
Loop |
|||
d = a + b |
|||
End Function |
|||
</source> |
</source> |
||
Версия от 18:45, 28 ноября 2011
Далее приводятся реализации алгоритма Евклида для вычисления НОД на различных языках программирования.
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):
return a if b == 0 else gcd(b, a % b)
Функция в нерекурсивном виде:
def gcd(a, b):
while b:
a, b = b, a % b
return a
Perl
Функция в рекурсивном виде:
sub nod
{
return $_[0] != 0 ? nod ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
Shell
Функция в рекурсивном виде:
nod()
{
n=1 a=$1 b=$2
if [[ $a -ne 0 ]]
then
nod $(($b%$a)) $a
let "n = $?"
else
let "n = $b"
fi
return $n
}
nod $1 $2
echo "NOD is $?"
Си
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? gcd(b, a % b) : a;
}
Алгоритм вычитанием:
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 (x `rem` y)
Глагол
ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; УКАЗ ПОКА (a # 0) И (b # 0) ВЫП ЕСЛИ a >= b ТО a := a ОСТАТОК b ИНАЧЕ b := b ОСТАТОК a КОН КОН; ВОЗВРАТ a + b КОН НОД;
Pascal
function nod( 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).
Erlang
gcd(A, 0) -> A; gcd(A, B) -> gcd(B, (A rem B)).
Java
public class GCD {
public static int gcd(int a,int b) {
while (b !=0) {
int tmp = a%b;
a = b;
b = tmp;
}
return a;
}
}
Также допустимы функции, аналогичные написанным выше на C, например так:
public class GCD {
public static int gcd(int a,int b) {
while(b!=0) b^=a^=b^=a%=b;
return a;
}
}
C#
int gcd(int a, int b)
{
while (b != 0)
b = a % (a = b);
return a;
}
MapBasic
Function NOD(a As Integer, b As Integer) As Integer
Dim d As Integer
Do While a <> 0 and b <> 0
If a >=b Then
a = a mod b
Else
b = b mod a
End If
Loop
d = a + b
End Function
Реализации бинарного алгоритма нахождения НОД
С
unsigned int gcd(unsigned int u, unsigned int v)
{
int shift;
/* GCD(0,x) := x */
if (u == 0 || v == 0)
return u | v;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
while ((v & 1) == 0) /* Loop X */
v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u < v) {
v -= u;
} else {
unsigned int diff = u - v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u << shift;
}
C#
long GCD(long a, long b)
{
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (a == 1 || b == 1) return 1;
if ((a % 2 == 0) && (b % 2 == 0)) return 2 * GCD(a / 2, b / 2);
if ((a % 2 == 0) && (b % 2 != 0)) return GCD(a / 2, b);
if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2);
return GCD(b, (long)Math.Abs(a - b));
}
Pascal/Delphi
function GCD(a, b: integer): integer;
begin
if (a = 0) then
begin
Result:= b;
Exit;
end else
if (b = 0) then
begin
Result:= a;
Exit;
end else
if (a = b) then
begin
Result:= a;
Exit;
end else
if (a = 1) or (b =1) then
begin
Result:= 1;
Exit;
end else
if (a mod 2 = 0) and (b mod 2 = 0) then
begin
Result:= 2*GCD(Trunc(a/2), Trunc(b/2));
Exit;
end else
if (a mod 2 = 0) and (b mod 2 <> 0) then
begin
Result:= GCD(Trunc(a/2), b);
Exit;
end else
if (a mod 2 <> 0) and (b mod 2 = 0) then
begin
Result:= GCD(a, Trunc(b/2));
Exit;
end;
Result:= GCD(b, Abs(a - b));
end;
Perl
sub nod
{
return $_[0] if $_[1] == 0;
return $_[1] if $_[0] == 0;
($u, $v)=@_; $g=1;$t=100;
while (1)
{
if ($u%2==1 || $v%2==1) {last;};
$u>>=1; ##(right shift)
$v>>=1;
$g<<=1; ## (left shift)
}
while ($u > 0)
{
if ($u%2==0 && $u>0) {$u = $u>>1;}
elsif ($v%2==0 && $v>0) {$v = $v>>1;}
else
{
$t = abs (($u-$v)/2);
if ($u < $v) {$v = $t;} else {$u = $t;}
}
}
return $v*$g;
}