Реализации алгоритмов/Алгоритм Евклида: различия между версиями

Содержимое удалено Содержимое добавлено
Тщательное оформление программного кода, примечаний, языки расположены в алфавитном порядке, добавлена программа для ПМК
Строка 1:
Далее приводятся реализации [[w:алгоритм Евклида|алгоритма Евклида]] для вычисления НОД на различных [[w:язык программирования|языках программирования]].
== [[Schemew:Бейсик|BASIC]] ==
===QBASIC, QuickBasic, VisualBasic (до версий с поддержкой .NET)===
Алгоритм вычитанием
Деление с остатком, без рекурсии:
 
<source lang="basic">
('''define''' gcd ('''lambda''' (a b)
Function GCD (a As Integer, b As Integer) As Integer
('''if''' (> a b) ('''gcd''' (- a b) b)
Dim d As Integer
('''if''' (< a b) ('''gcd''' a (- b a))
Do While a <> 0 and b <> a))))0
If a >=b Then
 
a = a mod b
== [[Ruby]] ==
Else
 
b = b mod a
Функция в [[рекурсия|рекурсивном]] виде:
End If
 
Loop
<source lang="ruby">
def GCD = gcd(a, + b)
End Function
return a if b.zero?
gcd(b, a % b)
end
</source>
 
==[[w:C (язык программирования)|C]]==
Функция в нерекурсивном виде:
Тип T определён как <code>typedef … T;</code>, вместо <code>…</code> следует подставить любой целочисленный тип (<code>int</code>, <code>unsigned</code>, <code>short</code> и т. д.)
 
Деление с остатком, без рекурсии:
<source lang="ruby">
<source lang="c">
def gcd(a, b)
T gcd (T a, b =T b,) a % b until b.zero?{
a T c;
while (b) {
end
c = a % b;
a = b;
b = c;
}
return (a < 0) ? -a : a;
}
</source>
 
Более короткое решение:
Алгоритм вычитанием:
<source lang="c">
 
T gcd (T a, T b) {
<source lang="ruby">
while (b)
def gcd(a, b)
if b ^= a ^= b ^= a >%= b;
return a -= b;
}
else
b -= a
end while a != b
a
end
</source>
 
Деление с остатком, рекурсия:
== [[PHP]] ==
<source lang="c">
 
T gcd (T a, T b) {
<source lang="php">
return (b == 0) ? a : gcd(b, a % b);
function nod($a, $b)
}
{
while ($a <> 0 && $b <> 0) {
if ($a > $b)
$a= $a % $b;
else
$b= $b % $a;
$nod= $a + $b;
}
return $nod;
}
echo nod(5,3);
</source>
 
Вычитание, без рекурсии:
== [[Python]] ==
<source lang="c">
 
T gcd (T a, T b) {
Функция в [[рекурсия|рекурсивном]] виде:
while (a != b) {
 
if (a > b)
<source lang="python">
a -= b;
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
b -= a;
}
return a;
}
</source>
 
==[[w:C_Sharp|C#]]==
Функция в нерекурсивном виде:
Деление с остатком, без рекурсии:
 
<source lang="pythoncsharp">
defint GCD gcd(int a, int b):
{
while b:
while a, (b != b, a % b0)
return b = a % (a = b);
return a;
}
</source>
 
== [[Perlw:Erlang|Erlang]] ==
Деление с остатком, рекурсия:
Функция в [[рекурсия|рекурсивном]] виде:
<source lang="erlang">
 
gcd(A, 0) -> A;
<source lang="perl">
gcd(A, B) -> gcd(B, (A rem B)).
sub nod
{
return $_[0] != 0 ? nod ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
</source>
 
==[[w:F_Sharp|F#]]==
== Shell ==
Деление с остатком, рекурсия:
 
<source lang="fsharp">
Функция в [[рекурсия|рекурсивном]] виде:
let rec nod a b =
 
match b with
<source lang="bash">
|0 -> a
 
|b -> nod b ()a {% b)
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 $?"
</source>
 
== [[Сиw:Forth (язык программирования)|СиForth]] (диалект [[RetroForth]])==
Деление с остатком, рекурсия:
 
<source lang="cforth"> int gcd(int a, int b) {
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;
int c;
while (b) {
c = a % b;
a = b;
b = c;
}
return fabs(a);
}</source>
 
Более короткое решение:
<source lang="c">
int gcd(int a, int b) {
while(b) b^=a^=b^=a%=b;
return a;
}</source>
 
Та же функция в рекурсивном виде:
<source lang="c">
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}</source>
 
Немного короче:
 
<source lang="c"> int gcd(int a, int b) {
return b? gcd(b, a % b) : a;
}
</source>
 
==[[w:Haskell|Haskell]]==
Алгоритм вычитанием:
Деление с остатком, рекурсия:
<source lang="c">
int gcd(int a, int b) {
while ( a != b) {
if (a > b) a -= b;
else b -= a;
}
return a;
}</source>
 
== [[Forth (язык программирования)|Форт]] (диалект [[RetroForth]]) ==
 
Рекурсивный алгоритм
 
: НОД ( n1 n2 -- n ) tuck mod 0; НОД ;
 
== [[Haskell]] ==
<source lang="haskell">
gcd :: Integral a => a -> a -> a
Строка 166 ⟶ 105 :
</source>
 
== [[F#w:Java|Java]] ==
Деление с остатком, без рекурсии:
Рекурсивный алгоритм
<source lang="java">
public static <T> T gcd (T a, T b) {
while (b != 0) {
T c = a % b;
a = b;
b = c;
}
return a;
}
</source>
 
Также допустимы функции, аналогичные написанным выше на C, например так:
<source lang="fsharp">
<source lang="java">
let rec nod a b =
public static <T> gcd (T a, T b) {
match b with
|0while ->(b a!= 0)
| b ->^= noda ^= b (^= a %= b);
return a;
}
</source>
''*короткая запись работает не корректно. Например при начальных значениях 34 и 9 уже на следующем шаге значения получаются 43 и 0...''
 
Деление с остатком, рекурсия:
<source lang="java">
public static <T> T gcd (T a, T b) {
return b == 0 ? a : gcd(b, a % b);
}
</source>
 
== [[Глаголw:Паскаль (язык программирования)|ГлаголPascal]] ==
Тип T определён как <code>type T = …;</code>, вместо <code>…</code> следует подставить любой целочисленный тип (<code>Integer</code>, <code>Byte</code>, <code>LongInt</code> и т. д.)
ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ;
 
УКАЗ
Деление с остатком, без рекурсии:
ПОКА (a # 0) И (b # 0) ВЫП
ЕСЛИ a >= b ТО
a := a ОСТАТОК b
ИНАЧЕ
b := b ОСТАТОК a
КОН
КОН;
ВОЗВРАТ a + b
КОН НОД;
== [[Паскаль (язык программирования)|Pascal]] ==
Обычный алгоритм:
<source lang="pascal">
function GCD function nod(a, b: longintT): longintT;
begin
while a * b <> 0 do
if a > b then
then a := a mod b
else
b := b mod a;
nod gcd := a + b;
end;
</source>
 
Более быстрый алгоритм:
<source lang="pascal">
function nodGCD (a, b: LongIntT): LongIntT;
var c: T;
var
begin
t: LongInt;
while b > 0 do
begin
while b > 0 dobegin
c := a mod b;
begin
t := a mod:= b;
a b := b;c
b := tend;
end; gcd := a
end;
nod := a;
end;
 
</source>
 
Деление с остатком, рекурсия:
В рекурсивном виде:
<source lang="pascal">
function gcd function nod(a, b: LongIntT): LongIntT;
begin
if b = 0 then
nod gcd := a
else
nod gcd := nod gcd(b, a mod b)
end;
</source>
 
==[[w:Perl|Perl]]==
== [[Пролог (язык программирования)|Prolog]] ==
Деление с остатком, рекурсия:
 
<source lang="perl">
?GCD(a,b,x)
sub gcd {
 
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
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]] ==
<source lang="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;
}
}
</source>
 
==[[w:PHP|PHP]]==
Немного короче:
Деление с остатком, без рекурсии:
<source lang="java">
<source lang="php">
public class GCD {
function gcd ($a, $b) {
public static int gcd(int a,int b) {
while ($a <> 0 return&& $b ==<> 0) ? a : gcd(b, a % b);{
if ($a > $b)
$a = $a % $b;
else
$b = $b % $a;
$gcd = $a + $b;
}
return $gcd;
}
echo gcd(5, 3);
</source>
 
==[[w:Пролог (язык программирования)|Prolog]]==
Также допустимы функции, аналогичные написанным выше на C, например так:
Деление с остатком, рекурсия:
<source lang="java">
<source lang="prolog">
public class GCD {
?GCD(a,b,x)
public static int gcd(int a,int b) {
while(b!=0) b^=a^=b^=a%=b;
return a;
}
}
</source>
''*короткая запись работает не корректно. Например при начальных значениях 34 и 9 уже на следующем шаге значения получаются 43 и 0...''
 
GCD(0,b,b) <-
== [[C#]] ==
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)
</code>
 
===[[w:SWI-Prolog]]===
<source lang="csharp">
Деление с остатком, рекурсия:
int gcd(int a, int b)
<source>
{
gcd(0,B,B).
while (b != 0)
gcd(A,0,A).
b = a % (a = b);
 
return 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).
</source>
 
== [[MapBasicw:Python|Python]] ==
Деление с остатком, без рекурсии:
<source lang="python">
def gcd (a, b):
while b:
a, b = b, a % b
return a
</source>
 
Деление с остатком, рекурсия:
<source lang="csharp">
<source lang="python">
Function NOD(a As Integer, b As Integer) As Integer
def gcd (a, b):
return a if b == 0 else gcd(b, a % b)
</source>
 
==[[:Ruby|Ruby]]==
Dim d As Integer
Деление с остатком, без рекурсии:
<source lang="ruby">
def gcd (a, b)
a, b = b, a % b until b.zero?
a
end
</source>
 
Деление с остатком, рекурсия:
Do While a <> 0 and b <> 0
<source lang="ruby">
def gcd (a, b)
return a if b.zero?
gcd(b, a % b)
end
</source>
 
Вычитание, без рекурсии:
If a >=b Then
<source lang="ruby">
a = a mod b
def gcd (a, b)
Else
b = b mod if a > b
a -= b
End If
else
b -= a
end while a != b
a
end
</source>
 
==[[w:Scheme|Scheme]]==
Loop
Вычитание, рекурсия:
('''define''' gcd ('''lambda''' (a b)
('''if''' (> a b) ('''gcd''' (- a b) b)
('''if''' (< a b) ('''gcd''' a (- b a))
a))))
 
==Shell==
d = a + b
Деление с остатком, рекурсия:
<source lang="bash">
gcd () {
n=1 a=$1 b=$2
if [[ $a -ne 0 ]]
then
gcd $(( $b % $a )) $a
let "n = $?"
else
let "n = $b"
fi
return $n
}
 
gcd $1 $2
End Function
echo "Greatest common divisor is $?"
</source>
 
==[[w:Глагол (язык программирования)|Глагол]]==
== Ассемблер ==
Деление с остатком, без рекурсии:
=== ARM ===
<source>
Алгоритм вычитанием
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
ПОКА (a # 0) И (b # 0) ВЫП
ЕСЛИ a >= b ТО
a := a ОСТАТОК b
ИНАЧЕ
b := b ОСТАТОК a
КОН
КОН;
ВОЗВРАТ a + b
КОН НОД;
</source>
 
==Ассемблер==
===ARM===
Вычитание, без рекурсии:
<source lang="arm">
loop CMP Ri, Rj ; проверка условий NE (i != j), GT (i > j) и LT (i < j);
Строка 328 ⟶ 318 :
</source>
 
=== Z80 ===
Вычитание, без рекурсии:
Алгоритм вычитанием
<source lang="z80">
GCD_DEHL: ;CALL Inputs: HL,DE; Output: DE
Строка 342 ⟶ 332 :
</source>
 
==Программируемые микрокалькуляторы «Электроника»==
== См. также ==
Деление с остатком, без рекурсии. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека.
 
Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе).
===МК-52 / 61 / 152 / 161===
<source>
00. Fx≠0 01. 13 02. ↔ 03. В↑ 04. FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. ×
10. − 11. Fx=0 12. 02 13. + 14. K|x| 15. С/П
</source>
 
==См. также==
* [[../Бинарный алгоритм вычисления НОД/]]