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

Примеры на Бейсике; исправления и форматирование
(Примеры на Бейсике; исправления и форматирование)
Далее приводятся реализацииРеализации [[w:алгоритм Евклида|алгоритма Евклида]] для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных [[w:язык программирования|языках программирования]].
 
==[[w:Язык_ассемблера|Assembler]]==
===ARM===
Вычитание, без рекурсии:
<source 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.
</source>
 
===Z80===
Вычитание, без рекурсии:
<source lang="z80">
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE
AND A ; сброс CF
LOOP:
SBC HL,DE ; совмещение трёх в одном - одного сравнения и поочередно двух вычитаний.
RET Z ; минимизация общего размера, поэтому в цикле.
JR NC,LOOP
ADD HL,DE ; откат лишнего вычитания
EX DE,HL
JR GCD_DEHL
</source>
 
==[[w:Бейсик|BASIC]]==
===QBASIC, QuickBasic, VisualBasic (до версий с поддержкой .NET)===
Деление с остатком, без рекурсии:
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты===
<source lang="basic">
10 INPUT "Two integer numbers"; A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
30 WHILE B% <> 0
40 A% = A% MOD B%
50 SWAP A%, B%
60 WEND
70 PRINT ABS(A%)
</source>
 
===[[w:QuickBasic|QuickBasic]] версий < 4.0, [[w:Turbo Basic|Turbo Basic]]===
<source lang="basic">
DEF FNGCD% (A%, B%)
DO WHILE B% <> 0
$gcdA% = $aA% +MOD $b;B%
ИНАЧЕSWAP A%, B%
LOOP
FNGCD% = ABS(A%)
END DEF
</source>
 
===[[w:PowerBASIC|PowerBASIC]], [[w:QBASIC|QBASIC]], [[w:QuickBasic|QuickBasic]], [[w:Visual Basic|Visual Basic]]===
<source lang="vb">
Function GCD (a As Integer, b As Integer) As Integer
Do While a <> 0 andAnd b <> 0
Dim d As Integer
Do While a <> 0 and b <> 0
If a > b Then
a = a modMod b
Else
b = b modMod a
End If
Loop
GCD = Abs(a + b) ' Для VB.NET следует заменить эту строку на Return Math.Abs(a + b)
GCD = a + b
End Function
</source>
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип T должен быть задан как:
Тип<source T определён как <codelang="c">typedef … T;</codesource>, вместо <code>…</code> следуетнужно подставить любой целочисленный тип (<code>int</code>, <code>unsigned</code>, <code>short</code> и т. д.)
'''C++:''' любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой:
<source lang="cpp">template < typename T ></source>
Для корректной обработки отрицательных чисел все последующие примеры используется функция вычисления модуля числа:
<source lang="c">
T abs (T value) {
return (value < (T)0) ? -value : value;
}
</source>
 
Деление с остатком, без рекурсии:
b = c;
}
return abs(a < 0) ? -a : a;
}
</source>
while (b)
b ^= a ^= b ^= a %= b;
return abs(a);
}
</source>
<source lang="c">
T gcd (T a, T b) {
return (b == 0) ? abs(a) : gcd(b, a % b);
}
</source>
<source lang="c">
T gcd (T a, T b) {
a = abs(a);
b = abs(b);
while (a != b) {
if (a > b)
while (b != 0)
b = a % (a = b);
return Math.Abs(a);
}
</source>
b = c;
}
return Math.abs(a);
}
</source>
while (b != 0)
b ^= a ^= b ^= a %= b;
return Math.abs(a);
}
</source>
<source lang="java">
public static <T> T gcd (T a, T b) {
return b == 0 ? Math.abs(a) : gcd(b, a % b);
}
</source>
else
b := b mod a;
GCD := Abs(a + b)
end;
</source>
b := c
end;
GCD := Abs(a)
end;
</source>
begin
if b = 0 then
GCD := Abs(a)
else
GCD := GCD(b, a mod b)
else
$b = $b % $a;
$gcd = $a + $b;
}
return abs($gcda + $b);
}
echo gcd(5, 3);
while b:
a, b = b, a % b
return abs(a)
</source>
 
<source lang="python">
def gcd (a, b):
return abs(a) if b == 0 else gcd(b, a % b)
</source>
 
def gcd (a, b)
a, b = b, a % b until b.zero?
a.abs
end
</source>
<source lang="ruby">
def gcd (a, b)
return a.abs if b.zero?
gcd(b, a % b)
end
<source lang="ruby">
def gcd (a, b)
a = a.abs
b = b.abs
if a > b
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
}
 
УКАЗ
ПОКА (a # 0) И (b # 0) ВЫП
ЕСЛИ a >=< b ТО
b := b ОСТАТОК a
ИНАЧЕ
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);
SUBGT Ri, Ri, Rj ; если GT, выполняется i = i-j;
SUBLT Rj, Rj, Ri ; если LT, выполняется j = j-i;
BNE loop ; если NE - переход на метку loop.
</source>
 
===Z80===
Вычитание, без рекурсии:
<source lang="z80">
GCD_DEHL: ;CALL Inputs: HL,DE; Output: DE
AND A ;сброс CF
LOOP:
SBC HL,DE ;совмещение трёх в одном - одного сравнения и поочередно двух вычитаний.
RET Z ;минимизация общего размера, поэтому в цикле.
JR NC,LOOP
ADD HL,DE ;откат лишнего вычитания
EX DE,HL
JR GCD_DEHL
</source>
 
Анонимный участник