Реализации алгоритмов/Алгоритм Евклида: различия между версиями
м →SWI-Prolog: текст ссылки в заголовке |
DannyS712 (обсуждение | вклад) м <source> -> <syntaxhighlight> (phab:T237267) |
||
Строка 27: | Строка 27: | ||
===ARM=== |
===ARM=== |
||
Вычитание, цикл: |
Вычитание, цикл: |
||
< |
<syntaxhighlight lang="arm"> |
||
loop CMP Ri, Rj ; проверка условий NE (i != j), GT (i > j) и LT (i < j); |
loop CMP Ri, Rj ; проверка условий NE (i != j), GT (i > j) и LT (i < j); |
||
SUBGT Ri, Ri, Rj ; если GT, выполняется i = i-j; |
SUBGT Ri, Ri, Rj ; если GT, выполняется i = i-j; |
||
SUBLT Rj, Rj, Ri ; если LT, выполняется j = j-i; |
SUBLT Rj, Rj, Ri ; если LT, выполняется j = j-i; |
||
BNE loop ; если NE - переход на метку loop. |
BNE loop ; если NE - переход на метку loop. |
||
</syntaxhighlight> |
|||
</source> |
|||
===Z80=== |
===Z80=== |
||
Вычитание, цикл: |
Вычитание, цикл: |
||
< |
<syntaxhighlight lang="z80"> |
||
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE |
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE |
||
AND A ; сброс CF |
AND A ; сброс CF |
||
Строка 46: | Строка 46: | ||
EX DE,HL |
EX DE,HL |
||
JR GCD_DEHL |
JR GCD_DEHL |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Бейсик|BASIC]]== |
==[[w:Бейсик|BASIC]]== |
||
===Классический=== |
===Классический=== |
||
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка): |
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка): |
||
< |
<syntaxhighlight lang="basic"> |
||
10 PRINT "Two integer numbers"; |
10 PRINT "Two integer numbers"; |
||
20 INPUT A, B |
20 INPUT A, B |
||
Строка 65: | Строка 65: | ||
120 PRINT A |
120 PRINT A |
||
130 END |
130 END |
||
</syntaxhighlight> |
|||
</source> |
|||
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты=== |
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты=== |
||
Цикл, деление с остатком: |
Цикл, деление с остатком: |
||
< |
<syntaxhighlight lang="basic"> |
||
10 INPUT "Two integer numbers", A%, B% |
10 INPUT "Two integer numbers", A%, B% |
||
20 PRINT "GCD("; A%; ", "; B%; ") = "; |
20 PRINT "GCD("; A%; ", "; B%; ") = "; |
||
Строка 77: | Строка 77: | ||
60 WEND |
60 WEND |
||
70 PRINT ABS(A%) |
70 PRINT ABS(A%) |
||
</syntaxhighlight> |
|||
</source> |
|||
===[[w:QuickBasic|QuickBasic]] версий < 4.0, [[w:Turbo Basic|Turbo Basic]]=== |
===[[w:QuickBasic|QuickBasic]] версий < 4.0, [[w:Turbo Basic|Turbo Basic]]=== |
||
Цикл, деление с остатком: |
Цикл, деление с остатком: |
||
< |
<syntaxhighlight lang="basic"> |
||
DEF FNGCD%(A%, B%) |
DEF FNGCD%(A%, B%) |
||
DO UNTIL B% = 0 |
DO UNTIL B% = 0 |
||
Строка 93: | Строка 93: | ||
FNGCD% = ABS(A%) |
FNGCD% = ABS(A%) |
||
END DEF |
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 для приложений]]=== |
===[[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 для приложений]]=== |
||
Строка 99: | Строка 99: | ||
Цикл, деление с остатком: |
Цикл, деление с остатком: |
||
< |
<syntaxhighlight lang="vb"> |
||
Function GCD(a As Long, b As Long) As Long |
Function GCD(a As Long, b As Long) As Long |
||
Do Until b = 0 |
Do Until b = 0 |
||
Строка 111: | Строка 111: | ||
GCD = a |
GCD = a |
||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсия, деление с остатком: |
Рекурсия, деление с остатком: |
||
< |
<syntaxhighlight lang="vb"> |
||
Function GCD(a As Long, b As Long) As Long |
Function GCD(a As Long, b As Long) As Long |
||
If b = 0 Then |
If b = 0 Then |
||
Строка 122: | Строка 122: | ||
End If |
End If |
||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</source> |
|||
===[[w:VB.NET|Visual Basic .NET]]=== |
===[[w:VB.NET|Visual Basic .NET]]=== |
||
Строка 128: | Строка 128: | ||
Цикл, деление с остатком: |
Цикл, деление с остатком: |
||
< |
<syntaxhighlight lang="vb"> |
||
Function GCD(ByVal a As Long, ByVal b As Long) As Long |
Function GCD(ByVal a As Long, ByVal b As Long) As Long |
||
Do Until b = 0 |
Do Until b = 0 |
||
Строка 137: | Строка 137: | ||
Return Math.Abs(a) |
Return Math.Abs(a) |
||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсия, деление с остатком: |
Рекурсия, деление с остатком: |
||
< |
<syntaxhighlight lang="vb"> |
||
Function GCD(ByVal a As Long, ByVal b As Long) As Long |
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 или более поздняя версия |
Return If(b = 0, Math.Abs(a), GCD(b, a Mod b)) ' VB.NET 2008 или более поздняя версия |
||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
||
'''C:''' Тип <code>Integer</code> должен быть задан как: |
'''C:''' Тип <code>Integer</code> должен быть задан как: |
||
< |
<syntaxhighlight lang="c">typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */</syntaxhighlight> |
||
'''C++:''' Любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой: |
'''C++:''' Любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой: |
||
< |
<syntaxhighlight lang="cpp">template <typename Integer></syntaxhighlight> |
||
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа: |
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer abs (Integer value) { |
Integer abs (Integer value) { |
||
return (value < 0) ? -value : value; |
return (value < 0) ? -value : value; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer gcd (Integer a, Integer b) { |
Integer gcd (Integer a, Integer b) { |
||
for (Integer c; b; ) { |
for (Integer c; b; ) { |
||
Строка 169: | Строка 169: | ||
return abs(a); |
return abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Без использования дополнительной переменной: |
Без использования дополнительной переменной: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer gcd (Integer a, Integer b) { |
Integer gcd (Integer a, Integer b) { |
||
while (b) |
while (b) |
||
Строка 178: | Строка 178: | ||
return abs(a); |
return abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний: |
Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer gcd (Integer a, Integer b) { |
Integer gcd (Integer a, Integer b) { |
||
if (!a) |
if (!a) |
||
Строка 193: | Строка 193: | ||
return abs(a); |
return abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer gcd (Integer a, Integer b) { |
Integer gcd (Integer a, Integer b) { |
||
return !b ? abs(a) : gcd(b, a % b); |
return !b ? abs(a) : gcd(b, a % b); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Вычитание, цикл: |
Вычитание, цикл: |
||
< |
<syntaxhighlight lang="c"> |
||
Integer gcd (Integer a, Integer b) { |
Integer gcd (Integer a, Integer b) { |
||
a = abs(a); |
a = abs(a); |
||
Строка 218: | Строка 218: | ||
return a; |
return a; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:C_Sharp|C#]], [[w:Java|Java]]== |
==[[w:C_Sharp|C#]], [[w:Java|Java]]== |
||
Строка 226: | Строка 226: | ||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="csharp"> |
||
static long GCD(long a, long b) |
static long GCD(long a, long b) |
||
{ |
{ |
||
Строка 233: | Строка 233: | ||
return Math.Abs(a); |
return Math.Abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
< |
<syntaxhighlight lang="csharp"> |
||
static long GCD(long a, long b) |
static long GCD(long a, long b) |
||
{ |
{ |
||
Строка 248: | Строка 248: | ||
return Math.Abs(a); |
return Math.Abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="csharp"> |
||
static long GCD (long a, long b) |
static long GCD (long a, long b) |
||
{ |
{ |
||
return b == 0 ? Math.Abs(a) : GCD(b, a % b); |
return b == 0 ? Math.Abs(a) : GCD(b, a % b); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Erlang|Erlang]]== |
==[[w:Erlang|Erlang]]== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="erlang"> |
||
gcd(A, 0) -> A; |
gcd(A, 0) -> A; |
||
gcd(A, B) -> gcd(B, (A rem B)). |
gcd(A, B) -> gcd(B, (A rem B)). |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:F_Sharp|F#]]== |
==[[w:F_Sharp|F#]]== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let rec gcd a b = |
let rec gcd a b = |
||
match b with |
match b with |
||
|0 -> a |
|0 -> a |
||
|b -> gcd b (a % b) |
|b -> gcd b (a % b) |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Forth (язык программирования)|Forth]] (диалект [[RetroForth]])== |
==[[w:Forth (язык программирования)|Forth]] (диалект [[RetroForth]])== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="forth"> |
||
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ; |
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ; |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Go|Go]]== |
==[[w:Go|Go]]== |
||
Тип <code>Integer</code> определён как: |
Тип <code>Integer</code> определён как: |
||
< |
<syntaxhighlight lang="go"> |
||
type Integer = int // Вместо int можно подставить любой другой целочисленный тип |
type Integer = int // Вместо int можно подставить любой другой целочисленный тип |
||
</syntaxhighlight> |
|||
</source> |
|||
Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа: |
Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа: |
||
< |
<syntaxhighlight lang="go"> |
||
func IntAbs(value Integer) Integer { |
func IntAbs(value Integer) Integer { |
||
if value < 0 { |
if value < 0 { |
||
Строка 294: | Строка 294: | ||
return value |
return value |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="go"> |
||
func GCD(a, b Integer) Integer { |
func GCD(a, b Integer) Integer { |
||
for b != 0 { |
for b != 0 { |
||
Строка 308: | Строка 308: | ||
return IntAbs(a) |
return IntAbs(a) |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="go"> |
||
func GCD(a, b Integer) Integer { |
func GCD(a, b Integer) Integer { |
||
if b == 0 { |
if b == 0 { |
||
Строка 318: | Строка 318: | ||
return GCD(b, a % b) |
return GCD(b, a % b) |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Haskell|Haskell]]== |
==[[w:Haskell|Haskell]]== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="haskell"> |
||
gcd :: Integral a => a -> a -> a |
gcd :: Integral a => a -> a -> a |
||
gcd 0 0 = error "НОД от 0 и 0 не определён." |
gcd 0 0 = error "НОД от 0 и 0 не определён." |
||
Строка 328: | Строка 328: | ||
where gcd' x 0 = x |
where gcd' x 0 = x |
||
gcd' x y = gcd' y (x `rem` y) |
gcd' x y = gcd' y (x `rem` y) |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:JavaScript|JavaScript]], [[w:ECMAScript|ECMAScript]]== |
==[[w:JavaScript|JavaScript]], [[w:ECMAScript|ECMAScript]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="js"> |
||
function gcd(a, b) { |
function gcd(a, b) { |
||
if (a === 0) |
if (a === 0) |
||
Строка 344: | Строка 344: | ||
return Math.abs(a); |
return Math.abs(a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="js"> |
||
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0 |
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0 |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Паскаль (язык программирования)|Pascal]]== |
==[[w:Паскаль (язык программирования)|Pascal]]== |
||
Тип <code>TInteger</code> определён как: |
Тип <code>TInteger</code> определён как: |
||
< |
<syntaxhighlight lang="pascal"> |
||
type TInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип } |
type TInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип } |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="pascal"> |
||
function GCD(a, b: TInteger): TInteger; |
function GCD(a, b: TInteger): TInteger; |
||
begin |
begin |
||
Строка 374: | Строка 374: | ||
GCD := Abs(a) |
GCD := Abs(a) |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="pascal"> |
||
function GCD(a, b: TInteger): TInteger; |
function GCD(a, b: TInteger): TInteger; |
||
begin |
begin |
||
Строка 385: | Строка 385: | ||
GCD := GCD(b, a mod b) |
GCD := GCD(b, a mod b) |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Perl|Perl]]== |
==[[w:Perl|Perl]]== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="perl"> |
||
sub gcd { |
sub gcd { |
||
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1]; |
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1]; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:PHP|PHP]]== |
==[[w:PHP|PHP]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="php"> |
||
function gcd ($a, $b) { |
function gcd ($a, $b) { |
||
if ($a === 0) |
if ($a === 0) |
||
Строка 409: | Строка 409: | ||
return abs($a); |
return abs($a); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Пролог (язык программирования)|Prolog]]== |
==[[w:Пролог (язык программирования)|Prolog]]== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="prolog"> |
||
?GCD(a, b, x) |
?GCD(a, b, x) |
||
Строка 420: | Строка 420: | ||
GCD(a, b, x) <- a >= b, m is a mod b, GCD(m, 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) |
GCD(a, b, x) <- a < b, m is b mod a, GCD(a, m, x) |
||
</syntaxhighlight> |
|||
</source> |
|||
===[[w:SWI-Prolog|SWI-Prolog]]=== |
===[[w:SWI-Prolog|SWI-Prolog]]=== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="prolog"> |
||
gcd(0, B, B). |
gcd(0, B, B). |
||
gcd(A, 0, A). |
gcd(A, 0, A). |
||
Строка 430: | Строка 430: | ||
gcd(A, B, X) :- A >= B, M is A mod B, gcd(M, 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). |
gcd(A, B, X) :- A < B, M is B mod A, gcd(A, M, X). |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Python|Python]]== |
==[[w:Python|Python]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="python"> |
||
def gcd(a: int, b: int) -> int: |
def gcd(a: int, b: int) -> int: |
||
while b: |
while b: |
||
a, b = b, a % b |
a, b = b, a % b |
||
return abs(a) |
return abs(a) |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="python"> |
||
def gcd(a: int, b: int) -> int: |
def gcd(a: int, b: int) -> int: |
||
return abs(a) if b == 0 else gcd(b, a % b) |
return abs(a) if b == 0 else gcd(b, a % b) |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[:Ruby|Ruby]]== |
==[[:Ruby|Ruby]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="ruby"> |
||
def gcd(a, b) |
def gcd(a, b) |
||
a, b = b, a % b until b.zero? |
a, b = b, a % b until b.zero? |
||
a.abs |
a.abs |
||
end |
end |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="ruby"> |
||
def gcd(a, b) |
def gcd(a, b) |
||
return a.abs if b.zero? |
return a.abs if b.zero? |
||
gcd(b, a % b) |
gcd(b, a % b) |
||
end |
end |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Rust (язык программирования)|Rust]]== |
==[[w:Rust (язык программирования)|Rust]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
< |
<syntaxhighlight lang="rust"> |
||
use num::Zero; |
use num::Zero; |
||
use std::ops::{RemAssign, Sub}; |
use std::ops::{RemAssign, Sub}; |
||
Строка 503: | Строка 503: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="rust"> |
||
use num::Zero; |
use num::Zero; |
||
use std::ops::{Rem, Sub}; |
use std::ops::{Rem, Sub}; |
||
Строка 524: | Строка 524: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Scheme|Scheme]]== |
==[[w:Scheme|Scheme]]== |
||
Строка 535: | Строка 535: | ||
==Shell== |
==Shell== |
||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
< |
<syntaxhighlight lang="bash"> |
||
gcd () { |
gcd () { |
||
n = 1 a = $1 b = $2 |
n = 1 a = $1 b = $2 |
||
Строка 550: | Строка 550: | ||
gcd $1 $2 |
gcd $1 $2 |
||
echo "Greatest common divisor is $?" |
echo "Greatest common divisor is $?" |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Глагол (язык программирования)|Глагол]]== |
==[[w:Глагол (язык программирования)|Глагол]]== |
||
Деление с остатком, цикл: |
Деление с остатком, цикл: |
||
<syntaxhighlight> |
|||
<source> |
|||
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ; |
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ; |
||
УКАЗ |
УКАЗ |
||
Строка 568: | Строка 568: | ||
ВОЗВРАТ МОДУЛЬ(a) |
ВОЗВРАТ МОДУЛЬ(a) |
||
КОН НОД; |
КОН НОД; |
||
</syntaxhighlight> |
|||
</source> |
|||
==Программируемые микрокалькуляторы «Электроника»== |
==Программируемые микрокалькуляторы «Электроника»== |
||
Строка 575: | Строка 575: | ||
===Б3-21, МК-46 / 64, МС-1103=== |
===Б3-21, МК-46 / 64, МС-1103=== |
||
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y. |
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y. |
||
<syntaxhighlight> |
|||
<source> |
|||
00. Px≠0 01. ↔ 02. − 03. Px≥0 04. F1 05. ↔ |
00. Px≠0 01. ↔ 02. − 03. Px≥0 04. F1 05. ↔ |
||
10. − 11. /−/ 12. ↔ 13. Px=0 14. Peⁱˣ 15. ↔ |
10. − 11. /−/ 12. ↔ 13. Px=0 14. Peⁱˣ 15. ↔ |
||
20. С/П |
20. С/П |
||
</syntaxhighlight> |
|||
</source> |
|||
===Б3-34, МК-54 / 56 / 61 / 52 / 161 / 163 / 152 / 1152=== |
===Б3-34, МК-54 / 56 / 61 / 52 / 161 / 163 / 152 / 1152=== |
||
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X, Y и X1. |
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека 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 |
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. С/П |
10. ↔ 11. Fx=0 12. 02 13. + 14. С/П |
||
</syntaxhighlight> |
|||
</source> |
|||
===МК-61 / 52 / 161 / 163 / 152 / 1152=== |
===МК-61 / 52 / 161 / 163 / 152 / 1152=== |
||
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют все регистры стека. |
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют все регистры стека. |
||
<syntaxhighlight> |
|||
<source> |
|||
00. Fx≠0 01. 13 02. ↔ 03. В↑ 04. FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. × |
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. С/П |
10. − 11. Fx=0 12. 02 13. + 14. K|x| 15. С/П |
||
</syntaxhighlight> |
|||
</source> |
|||
==См. также== |
==См. также== |
Версия от 15:56, 16 апреля 2020
Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных языках программирования.
Описание
Классический алгоритм Евклида применяется к паре неотрицательных целых чисел. Пока ни одно из чисел в паре не равно нулю, из большего числа вычитается меньшее; вычитаемое и полученная разность формируют новую пару. Действие повторяется, пока один из элементов пары не обратится в 0, тогда значение другого будет равно искомому НОД.
Рекурсивная формулировка классического алгоритма:
- НОД(a, 0) = a
- НОД(a, b) = НОД(a, a − b) при a ≥ b
- НОД(a, b) = НОД(b, b − a) при a < b
Несложно заметить, что последовательное вычитание из большего числа меньшего, пока разность не станет меньше вычитаемого, соответствует нахождению остатка от деления большего числа на меньшее. На этом основан так называемый быстрый алгоритм Евклида: в паре чисел одно число делится с остатком на второе; делитель и полученный остаток формируют новую пару. Действие повторяется, пока один из элементов пары не обратится в 0, тогда значение другого будет равно искомому НОД.
Рекурсивная формулировка быстрого алгоритма:
- НОД(a, 0) = a
- НОД(a, b) = НОД(b, ОСТАТОК(b / a))
Оба алгоритма обобщаются на ноль и отрицательные значения. При этом следует иметь ввиду:
- Помимо положительных общих делителей у чисел имеются и отрицательные. Однако наибольший общий делитель по определению не может быть отрицательным (очевидно, что любое положительное число больше любого отрицательного). Таким образом НОД двух чисел равен НОДу их модулей.
- Если одно из чисел в паре равно нулю, а другое — нет, то их НОД равен модулю ненулевого числа.
- НОД пары нулей может рассматриваться, как неопределённое значение или бесконечность, а может приниматься равным нулю. Приведённые реализации в основном придерживаются последнего подхода (технически он реализуется проще).
- Подавляющее большинство языков программирования представляют отрицательные целые числа в так называемом дополнительном коде, при этом у наименьшего отрицательного значения типа отсутствует парное положительное значение (например наименьшее значение 16-битного знакового целого — −32768, а наибольшее — 32767). Следовательно вычисление НОД с применением наименьшего значения знакового типа может вызывать переполнение и давать неверные результаты.
Как правило, языки программирования включают функцию или оператор нахождения остатка от деления двух чисел, поэтому соответствующие реализации используют именно быстрый алгоритм Евклида. Алгоритм, построенный на вычитании, имеет смысл использовать на тех системах, где встроенная операция нахождения остатка отсутствует и её невыгодно эмулировать, например, через деление и взятие целой части.
Реализации
Assembler
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.
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
BASIC
Классический
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):
10 PRINT "Two integer numbers";
20 INPUT A, B
30 PRINT "GCD("; A; ", "; B,") = ";
40 LET A = ABS(A)
50 IF B = 0 THEN GOTO 120
60 LET B = ABS(B)
70 IF A < B THEN GOTO 90
80 LET A = A - B: GOTO 70
90 IF A = 0 THEN LET A = B: GOTO 120
100 LET B = B - A: IF B >= A THEN GOTO 100
110 IF B > 0 THEN GOTO 80
120 PRINT A
130 END
GW-BASIC и совместимые диалекты
Цикл, деление с остатком:
10 INPUT "Two integer numbers", A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
30 WHILE B% <> 0
40 A% = A% MOD B%
50 IF A% = 0 THEN A% = B%: B% = 0: ELSE B% = B% MOD A%
60 WEND
70 PRINT ABS(A%)
QuickBasic версий < 4.0, Turbo Basic
Цикл, деление с остатком:
DEF FNGCD%(A%, B%)
DO UNTIL B% = 0
A% = A% MOD B%
IF A% = 0 THEN
FNGCD% = ABS(B%)
EXIT DEF
END IF
B% = B% MOD A%
LOOP
FNGCD% = ABS(A%)
END DEF
PowerBASIC, QBASIC, QuickBasic версий 4.X, Visual Basic версий ≤ 6.0, Visual Basic для приложений
В следующих примерах используется тип Long
(длинное целое); вместо него можно применять также тип Integer
(стандартное целое).
Цикл, деление с остатком:
Function GCD(a As Long, b As Long) As Long
Do Until b = 0
a = a Mod b
If a = 0 Then
GCD = b
Exit Function
End If
b = b Mod a
Loop
GCD = a
End Function
Рекурсия, деление с остатком:
Function GCD(a As Long, b As Long) As Long
If b = 0 Then
GCD = Abs(a)
Else
GCD = GCD(b, a Mod b)
End If
End Function
Visual Basic .NET
В следующих примерах используется тип Long
(длинное целое); вместо него можно применять любые другие целочисленные типы платформы .NET.
Цикл, деление с остатком:
Function GCD(ByVal a As Long, ByVal b As Long) As Long
Do Until b = 0
a = a Mod b
If a = 0 Then Return Math.Abs(b)
b = b Mod a
Loop
Return Math.Abs(a)
End Function
Рекурсия, деление с остатком:
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
C/C++
C: Тип Integer
должен быть задан как:
typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */
C++: Любую из нижеприведённых функций (включая abs
) следует предварить строкой:
template <typename Integer>
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:
Integer abs (Integer value) {
return (value < 0) ? -value : value;
}
Деление с остатком, цикл:
Integer gcd (Integer a, Integer b) {
for (Integer c; b; ) {
c = a % b;
a = b;
b = c;
}
return abs(a);
}
Без использования дополнительной переменной:
Integer gcd (Integer a, Integer b) {
while (b)
b ^= a ^= b ^= a %= b;
return abs(a);
}
Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний:
Integer gcd (Integer a, Integer b) {
if (!a)
return abs(b);
if (!b)
return abs(a);
for ( ; ; )
if (!(a %= b))
return abs(b);
else if (!(b %= a))
return abs(a);
}
Деление с остатком, рекурсия:
Integer gcd (Integer a, Integer b) {
return !b ? abs(a) : gcd(b, a % b);
}
Вычитание, цикл:
Integer gcd (Integer a, Integer b) {
a = abs(a);
b = abs(b);
while (b) {
while (a >= b)
a -= b;
if (!a)
return b;
do {
b -= a;
} while (b >= a);
}
return a;
}
C#, Java
Приведён код для C#. Для Java следует заменить Abs
на abs
и, для соответствия правилам оформления кода, переименовать функции в gcd
и перенести {
в конец предыдущей строки.
Вместо long
можно использовать и другие целочисленные типы — byte
, int
и т. д.
Деление с остатком, цикл:
static long GCD(long a, long b)
{
while (b != 0)
b = a % (a = b);
return Math.Abs(a);
}
static long GCD(long a, long b)
{
if (a == 0)
return Math.Abs(b);
if (b == 0)
return Math.Abs(a);
for ( ; ; )
if ((a %= b) == 0)
return Math.Abs(b);
else if ((b %= a) == 0)
return Math.Abs(a);
}
Деление с остатком, рекурсия:
static long GCD (long a, long b)
{
return b == 0 ? Math.Abs(a) : GCD(b, a % b);
}
Erlang
Деление с остатком, рекурсия:
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).
F#
Деление с остатком, рекурсия:
let rec gcd a b =
match b with
|0 -> a
|b -> gcd b (a % b)
Forth (диалект RetroForth)
Деление с остатком, рекурсия:
: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;
Go
Тип Integer
определён как:
type Integer = int // Вместо int можно подставить любой другой целочисленный тип
Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа:
func IntAbs(value Integer) Integer {
if value < 0 {
return -value
}
return value
}
Деление с остатком, цикл:
func GCD(a, b Integer) Integer {
for b != 0 {
a %= b
if a == 0 {
return IntAbs(b)
}
b %= a
}
return IntAbs(a)
}
Деление с остатком, рекурсия:
func GCD(a, b Integer) Integer {
if b == 0 {
return IntAbs(a)
}
return GCD(b, a % b)
}
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)
JavaScript, ECMAScript
Деление с остатком, цикл:
function gcd(a, b) {
if (a === 0)
return Math.abs(b);
if (b === 0)
return Math.abs(a);
for ( ; ; )
if ((a %= b) === 0)
return Math.abs(b);
else if ((b %= a) === 0)
return Math.abs(a);
}
Деление с остатком, рекурсия:
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0
Pascal
Тип TInteger
определён как:
type TInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
Деление с остатком, цикл:
function GCD(a, b: TInteger): TInteger;
begin
while b <> 0 do
begin
a := a mod b;
if a = 0 then
begin
a := b;
b := 0
end
else
b := b mod a
end;
GCD := Abs(a)
end;
Деление с остатком, рекурсия:
function GCD(a, b: TInteger): TInteger;
begin
if b = 0 then
GCD := Abs(a)
else
GCD := GCD(b, a mod b)
end;
Perl
Деление с остатком, рекурсия:
sub gcd {
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
PHP
Деление с остатком, цикл:
function gcd ($a, $b) {
if ($a === 0)
return abs($b);
if ($b === 0)
return abs($a)
for ( ; ; )
if (($a %= $b) === 0)
return abs($b);
else if (($b %= $a) === 0)
return abs($a);
}
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).
Python
Деление с остатком, цикл:
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return abs(a)
Деление с остатком, рекурсия:
def gcd(a: int, b: int) -> int:
return abs(a) if b == 0 else gcd(b, a % b)
Ruby
Деление с остатком, цикл:
def gcd(a, b)
a, b = b, a % b until b.zero?
a.abs
end
Деление с остатком, рекурсия:
def gcd(a, b)
return a.abs if b.zero?
gcd(b, a % b)
end
Rust
Деление с остатком, цикл:
use num::Zero;
use std::ops::{RemAssign, Sub};
fn gcd <Integer> (a: Integer, b: Integer) -> Integer
where Integer: Zero + PartialOrd + Sub<Output = Integer> + RemAssign + Copy
{
let result: Integer;
if a.is_zero() {
result = b;
} else if b.is_zero() {
result = a;
} else {
// Вместо неизменяемых параметров a и b дальше используются переменные _a и _b
let mut _a = a;
let mut _b = b;
loop {
_a %= _b;
if _a.is_zero() {
result = _b;
break;
};
_b %= _a;
if _b.is_zero() {
result = _a;
break;
};
};
};
// `result` берётся по модулю
if result < Integer::zero() {
Integer::zero() - result
} else {
result
}
}
Деление с остатком, рекурсия:
use num::Zero;
use std::ops::{Rem, Sub};
pub fn gcd <Integer> (a: Integer, b: Integer) -> Integer
where Integer: Zero + PartialOrd + Sub<Output = Integer> + Rem<Output = Integer> + Copy
{
if b.is_zero() {
// Возвращаемое значение берётся по модулю
if a < Integer::zero() {
Integer::zero() - a
} else {
a
}
} else {
gcd(b, a % b)
}
}
Scheme
Вычитание, рекурсия:
(define gcd (lambda (a b) (if (> a b) (gcd (- a b) b) (if (< a b) (gcd a (- b a)) a))))
Shell
Деление с остатком, рекурсия:
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 $?"
Глагол
Деление с остатком, цикл:
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
ПОКА b # 0 ВЫП
a := a ОСТАТОК b;
ЕСЛИ a = 0 ТО
a := b;
b := 0
ИНАЧЕ
b := b ОСТАТОК a
КОН
КОН;
ВОЗВРАТ МОДУЛЬ(a)
КОН НОД;
Программируемые микрокалькуляторы «Электроника»
Использование: <первое число> → регистр Y, <второе число> → регистр X, В/О, С/П (НОД на индикаторе).
Б3-21, МК-46 / 64, МС-1103
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.
00. Px≠0 01. ↔ 02. − 03. Px≥0 04. F1 05. ↔
10. − 11. /−/ 12. ↔ 13. Px=0 14. Peⁱˣ 15. ↔
20. С/П
Б3-34, МК-54 / 56 / 61 / 52 / 161 / 163 / 152 / 1152
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X, Y и X1.
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. С/П
МК-61 / 52 / 161 / 163 / 152 / 1152
Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют все регистры стека.
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. С/П