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

м
<source> -> <syntaxhighlight> (phab:T237267)
м (→‎SWI-Prolog: текст ссылки в заголовке)
м (<source> -> <syntaxhighlight> (phab:T237267))
===ARM===
Вычитание, цикл:
<sourcesyntaxhighlight lang="arm">
loop CMP Ri, Rj ; проверка условий NE (i != j), GT (i > j) и LT (i < j);
SUBGT Ri, Ri, Rj ; если GT, выполняется i = i-j;
SUBLT Rj, Rj, Ri ; если LT, выполняется j = j-i;
BNE loop ; если NE - переход на метку loop.
</syntaxhighlight>
</source>
 
===Z80===
Вычитание, цикл:
<sourcesyntaxhighlight lang="z80">
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE
AND A ; сброс CF
EX DE,HL
JR GCD_DEHL
</syntaxhighlight>
</source>
 
==[[w:Бейсик|BASIC]]==
===Классический===
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):
<sourcesyntaxhighlight lang="basic">
10 PRINT "Two integer numbers";
20 INPUT A, B
120 PRINT A
130 END
</syntaxhighlight>
</source>
 
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты===
Цикл, деление с остатком:
<sourcesyntaxhighlight lang="basic">
10 INPUT "Two integer numbers", A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
60 WEND
70 PRINT ABS(A%)
</syntaxhighlight>
</source>
 
===[[w:QuickBasic|QuickBasic]] версий < 4.0, [[w:Turbo Basic|Turbo Basic]]===
Цикл, деление с остатком:
<sourcesyntaxhighlight lang="basic">
DEF FNGCD%(A%, B%)
DO UNTIL B% = 0
FNGCD% = ABS(A%)
END DEF
</syntaxhighlight>
</source>
 
===[[w:PowerBASIC|PowerBASIC]], [[w:QBASIC|QBASIC]], [[w:QuickBasic|QuickBasic]] версий 4.X, [[w:Visual Basic|Visual Basic]] версий ≤ 6.0, [[w:Visual Basic for Applications|Visual Basic для приложений]]===
 
Цикл, деление с остатком:
<sourcesyntaxhighlight lang="vb">
Function GCD(a As Long, b As Long) As Long
Do Until b = 0
GCD = a
End Function
</syntaxhighlight>
</source>
 
Рекурсия, деление с остатком:
<sourcesyntaxhighlight lang="vb">
Function GCD(a As Long, b As Long) As Long
If b = 0 Then
End If
End Function
</syntaxhighlight>
</source>
 
===[[w:VB.NET|Visual Basic .NET]]===
 
Цикл, деление с остатком:
<sourcesyntaxhighlight lang="vb">
Function GCD(ByVal a As Long, ByVal b As Long) As Long
Do Until b = 0
Return Math.Abs(a)
End Function
</syntaxhighlight>
</source>
 
Рекурсия, деление с остатком:
<sourcesyntaxhighlight lang="vb">
Function GCD(ByVal a As Long, ByVal b As Long) As Long
Return If(b = 0, Math.Abs(a), GCD(b, a Mod b)) ' VB.NET 2008 или более поздняя версия
End Function
</syntaxhighlight>
</source>
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип <code>Integer</code> должен быть задан как:
<sourcesyntaxhighlight lang="c">typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */</sourcesyntaxhighlight>
 
'''C++:''' Любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой:
<sourcesyntaxhighlight lang="cpp">template <typename Integer></sourcesyntaxhighlight>
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:
<sourcesyntaxhighlight lang="c">
Integer abs (Integer value) {
return (value < 0) ? -value : value;
}
</syntaxhighlight>
</source>
 
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="c">
Integer gcd (Integer a, Integer b) {
for (Integer c; b; ) {
return abs(a);
}
</syntaxhighlight>
</source>
 
Без использования дополнительной переменной:
<sourcesyntaxhighlight lang="c">
Integer gcd (Integer a, Integer b) {
while (b)
return abs(a);
}
</syntaxhighlight>
</source>
 
Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний:
<sourcesyntaxhighlight lang="c">
Integer gcd (Integer a, Integer b) {
if (!a)
return abs(a);
}
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="c">
Integer gcd (Integer a, Integer b) {
return !b ? abs(a) : gcd(b, a % b);
}
</syntaxhighlight>
</source>
 
Вычитание, цикл:
<sourcesyntaxhighlight lang="c">
Integer gcd (Integer a, Integer b) {
a = abs(a);
return a;
}
</syntaxhighlight>
</source>
 
==[[w:C_Sharp|C#]], [[w:Java|Java]]==
 
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="csharp">
static long GCD(long a, long b)
{
return Math.Abs(a);
}
</syntaxhighlight>
</source>
 
<sourcesyntaxhighlight lang="csharp">
static long GCD(long a, long b)
{
return Math.Abs(a);
}
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="csharp">
static long GCD (long a, long b)
{
return b == 0 ? Math.Abs(a) : GCD(b, a % b);
}
</syntaxhighlight>
</source>
 
==[[w:Erlang|Erlang]]==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="erlang">
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).
</syntaxhighlight>
</source>
 
==[[w:F_Sharp|F#]]==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="fsharp">
let rec gcd a b =
match b with
|0 -> a
|b -> gcd b (a % b)
</syntaxhighlight>
</source>
 
==[[w:Forth (язык программирования)|Forth]] (диалект [[RetroForth]])==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="forth">
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;
</syntaxhighlight>
</source>
 
==[[w:Go|Go]]==
Тип <code>Integer</code> определён как:
<sourcesyntaxhighlight lang="go">
type Integer = int // Вместо int можно подставить любой другой целочисленный тип
</syntaxhighlight>
</source>
 
Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа:
<sourcesyntaxhighlight lang="go">
func IntAbs(value Integer) Integer {
if value < 0 {
return value
}
</syntaxhighlight>
</source>
 
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="go">
func GCD(a, b Integer) Integer {
for b != 0 {
return IntAbs(a)
}
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="go">
func GCD(a, b Integer) Integer {
if b == 0 {
return GCD(b, a % b)
}
</syntaxhighlight>
</source>
 
==[[w:Haskell|Haskell]]==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="haskell">
gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД от 0 и 0 не определён."
where gcd' x 0 = x
gcd' x y = gcd' y (x `rem` y)
</syntaxhighlight>
</source>
 
==[[w:JavaScript|JavaScript]], [[w:ECMAScript|ECMAScript]]==
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="js">
function gcd(a, b) {
if (a === 0)
return Math.abs(a);
}
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="js">
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0
</syntaxhighlight>
</source>
 
==[[w:Паскаль (язык программирования)|Pascal]]==
Тип <code>TInteger</code> определён как:
<sourcesyntaxhighlight lang="pascal">
type TInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
</syntaxhighlight>
</source>
 
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="pascal">
function GCD(a, b: TInteger): TInteger;
begin
GCD := Abs(a)
end;
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="pascal">
function GCD(a, b: TInteger): TInteger;
begin
GCD := GCD(b, a mod b)
end;
</syntaxhighlight>
</source>
 
==[[w:Perl|Perl]]==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="perl">
sub gcd {
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
</syntaxhighlight>
</source>
 
==[[w:PHP|PHP]]==
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="php">
function gcd ($a, $b) {
if ($a === 0)
return abs($a);
}
</syntaxhighlight>
</source>
 
==[[w:Пролог (язык программирования)|Prolog]]==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="prolog">
?GCD(a, b, x)
 
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)
</syntaxhighlight>
</source>
 
===[[w:SWI-Prolog|SWI-Prolog]]===
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="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).
</syntaxhighlight>
</source>
 
==[[w:Python|Python]]==
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="python">
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return abs(a)
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="python">
def gcd(a: int, b: int) -> int:
return abs(a) if b == 0 else gcd(b, a % b)
</syntaxhighlight>
</source>
 
==[[:Ruby|Ruby]]==
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="ruby">
def gcd(a, b)
a, b = b, a % b until b.zero?
a.abs
end
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="ruby">
def gcd(a, b)
return a.abs if b.zero?
gcd(b, a % b)
end
</syntaxhighlight>
</source>
 
==[[w:Rust (язык программирования)|Rust]]==
Деление с остатком, цикл:
<sourcesyntaxhighlight lang="rust">
use num::Zero;
use std::ops::{RemAssign, Sub};
}
}
</syntaxhighlight>
</source>
 
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="rust">
use num::Zero;
use std::ops::{Rem, Sub};
}
}
</syntaxhighlight>
</source>
 
==[[w:Scheme|Scheme]]==
==Shell==
Деление с остатком, рекурсия:
<sourcesyntaxhighlight lang="bash">
gcd () {
n = 1 a = $1 b = $2
gcd $1 $2
echo "Greatest common divisor is $?"
</syntaxhighlight>
</source>
 
==[[w:Глагол (язык программирования)|Глагол]]==
Деление с остатком, цикл:
<syntaxhighlight>
<source>
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
ВОЗВРАТ МОДУЛЬ(a)
КОН НОД;
</syntaxhighlight>
</source>
 
==Программируемые микрокалькуляторы «Электроника»==
===Б3-21, МК-46 / 64, МС-1103===
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.
<syntaxhighlight>
<source>
00. Px≠0 01. ↔ 02. − 03. Px≥0 04. F1 05. ↔
10. − 11. /−/ 12. ↔ 13. Px=0 14. Peⁱˣ 15. ↔
20. С/П
</syntaxhighlight>
</source>
 
===Б3-34, МК-54 / 56 / 61 / 52 / 161 / 163 / 152 / 1152===
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X, Y и X1.
<syntaxhighlight>
<source>
00. Fx≠0 01. 13 02. − 03. Fx<0 04. 09 05. /−/ 06. FВx 07. ↔ 08. − 09. FВx
10. ↔ 11. Fx=0 12. 02 13. + 14. С/П
</syntaxhighlight>
</source>
 
===МК-61 / 52 / 161 / 163 / 152 / 1152===
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют все регистры стека.
<syntaxhighlight>
<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. С/П
</syntaxhighlight>
</source>
 
==См. также==
583

правки