Реализации алгоритмов/Алгоритм Евклида: различия между версиями
Содержимое удалено Содержимое добавлено
Тщательное оформление программного кода, примечаний, языки расположены в алфавитном порядке, добавлена программа для ПМК |
|||
Строка 1:
Далее приводятся реализации [[w:алгоритм Евклида|алгоритма Евклида]] для вычисления НОД на различных [[w:язык программирования|языках программирования]].
==
===QBASIC, QuickBasic, VisualBasic (до версий с поддержкой .NET)===
Деление с остатком, без рекурсии:
<source lang="basic">
Function GCD (a As Integer, b As Integer) As Integer
Dim d As Integer
Do While a <> 0 and b <>
If a >=b Then
a = a mod b
Else
b = b mod a
End If
Loop
End Function
</source>
==[[w:C (язык программирования)|C]]==
Тип T определён как <code>typedef … T;</code>, вместо <code>…</code> следует подставить любой целочисленный тип (<code>int</code>, <code>unsigned</code>, <code>short</code> и т. д.)
Деление с остатком, без рекурсии:
<source lang="c">
T gcd (T a,
while (b) {
c = a % b;
a = b;
b = c;
}
return (a < 0) ? -a : a;
}
</source>
Более короткое решение:
<source lang="c">
T gcd (T a, T b) {
while (b)
return a
}
</source>
Деление с остатком, рекурсия:
<source lang="c">
T gcd (T a, T b) {
return (b == 0) ? a : gcd(b, a % b);
}
</source>
Вычитание, без рекурсии:
<source lang="c">
T gcd (T a, T b) {
while (a != b) {
if (a > b)
a -= b;
b -= a;
}
return a;
}
</source>
==[[w:C_Sharp|C#]]==
Деление с остатком, без рекурсии:
<source lang="
{
while
return a;
}
</source>
==
Деление с остатком, рекурсия:
<source lang="erlang">
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).
</source>
==[[w:F_Sharp|F#]]==
Деление с остатком, рекурсия:
<source lang="fsharp">
let rec nod a b =
match b with
|0 -> a
|b -> nod b (
</source>
==
Деление с остатком, рекурсия:
<source lang="
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;
</source>
==[[w:Haskell|Haskell]]==
Деление с остатком, рекурсия:
<source lang="haskell">
gcd :: Integral a => a -> a -> a
Строка 166 ⟶ 105 :
</source>
==
Деление с остатком, без рекурсии:
<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="java">
public static <T> gcd (T a, T 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>
==
Тип T определён как <code>type T = …;</code>, вместо <code>…</code> следует подставить любой целочисленный тип (<code>Integer</code>, <code>Byte</code>, <code>LongInt</code> и т. д.)
Деление с остатком, без рекурсии:
<source lang="pascal">
function GCD
while a * b <> 0 do
if a > b then
else
b := b mod a; </source>
Более быстрый алгоритм:
<source lang="pascal">
var c: T;
begin
while b > 0 do
c := a mod b;
end;
</source>
Деление с остатком, рекурсия:
<source lang="pascal">
function gcd
if b = 0 then
else
</source>
==[[w:Perl|Perl]]==
Деление с остатком, рекурсия:
<source lang="perl">
sub gcd {
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
</source>
==[[w:PHP|PHP]]==
Деление с остатком, без рекурсии:
<source lang="php">
function gcd ($a, $b) {
while ($a <> 0
if ($a > $b)
$a = $a % $b;
else
$b = $b % $a;
$gcd = $a + $b;
}
return $gcd;
}
echo gcd(5, 3);
</source>
==[[w:Пролог (язык программирования)|Prolog]]==
Деление с остатком, рекурсия:
<source lang="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)
</code>
===[[w:SWI-Prolog]]===
Деление с остатком, рекурсия:
<source>
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).
</source>
==
Деление с остатком, без рекурсии:
<source lang="python">
def gcd (a, b):
while b:
a, b = b, a % b
return a
</source>
Деление с остатком, рекурсия:
<source lang="python">
def gcd (a, b):
return a if b == 0 else gcd(b, a % b)
</source>
==[[:Ruby|Ruby]]==
Деление с остатком, без рекурсии:
<source lang="ruby">
def gcd (a, b)
a, b = b, a % b until b.zero?
a
end
</source>
Деление с остатком, рекурсия:
<source lang="ruby">
def gcd (a, b)
return a if b.zero?
gcd(b, a % b)
end
</source>
Вычитание, без рекурсии:
<source lang="ruby">
def gcd (a, b)
a -= b
else
b -= a
end while a != b
a
end
</source>
==[[w:Scheme|Scheme]]==
Вычитание, рекурсия:
('''define''' gcd ('''lambda''' (a b)
('''if''' (> a b) ('''gcd''' (- a b) b)
('''if''' (< a b) ('''gcd''' a (- b a))
a))))
==Shell==
Деление с остатком, рекурсия:
<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
echo "Greatest common divisor is $?"
</source>
==[[w:Глагол (язык программирования)|Глагол]]==
Деление с остатком, без рекурсии:
<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>
===
Вычитание, без рекурсии:
<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>
==См. также==
* [[../Бинарный алгоритм вычисления НОД/]]
|