Реализации алгоритмов/Алгоритм Евклида: различия между версиями
Добавлены реализации и примеры их использования на Rust |
Нет описания правки |
||
Строка 3: | Строка 3: | ||
==[[w:Язык_ассемблера|Assembler]]== |
==[[w:Язык_ассемблера|Assembler]]== |
||
===ARM=== |
===ARM=== |
||
Вычитание, |
Вычитание, цикл: |
||
<source lang="arm"> |
<source 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); |
||
Строка 12: | Строка 12: | ||
===Z80=== |
===Z80=== |
||
Вычитание, |
Вычитание, цикл: |
||
<source lang="z80"> |
<source lang="z80"> |
||
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE |
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE |
||
Строка 26: | Строка 26: | ||
==[[w:Бейсик|BASIC]]== |
==[[w:Бейсик|BASIC]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты=== |
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты=== |
||
<source lang="basic"> |
<source lang="basic"> |
||
Строка 76: | Строка 76: | ||
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
||
'''C:''' Тип |
'''C:''' Тип <code>IntType</code> должен быть задан как: |
||
<source lang="c">typedef |
<source lang="c">typedef int IntType; /* Вместо int можно подставить любой другой целочисленный тип */</source> |
||
Вместо <code>…</code> нужно подставить любой целочисленный тип (<code>int</code>, <code>unsigned</code>, <code>short</code> и т. д.) |
|||
'''C++:''' |
'''C++:''' Любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой: |
||
<source lang="cpp">template < typename |
<source lang="cpp">template < typename IntType ></source> |
||
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа: |
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа: |
||
<source lang="c"> |
<source lang="c"> |
||
IntType abs (IntType value) { |
|||
return (value < |
return (value < 0) ? -value : value; |
||
} |
} |
||
</source> |
</source> |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="c"> |
<source lang="c"> |
||
IntType gcd (IntType a, IntType b) { |
|||
IntType c; |
|||
while (b) { |
while (b) { |
||
c = a % b; |
c = a % b; |
||
Строка 104: | Строка 103: | ||
Более короткое решение: |
Более короткое решение: |
||
<source lang="c"> |
<source lang="c"> |
||
IntType gcd (IntType a, IntType b) { |
|||
while (b) |
while (b) |
||
b ^= a ^= b ^= a %= b; |
b ^= a ^= b ^= a %= b; |
||
Строка 113: | Строка 112: | ||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
<source lang="c"> |
<source lang="c"> |
||
IntType gcd (IntType a, IntType b) { |
|||
return (b == 0) ? abs(a) : gcd(b, a % b); |
return (b == 0) ? abs(a) : gcd(b, a % b); |
||
} |
} |
||
</source> |
</source> |
||
Вычитание, |
Вычитание, цикл: |
||
<source lang="c"> |
<source lang="c"> |
||
IntType gcd (IntType a, IntType b) { |
|||
a = abs(a); |
a = abs(a); |
||
b = abs(b); |
b = abs(b); |
||
Строка 133: | Строка 132: | ||
</source> |
</source> |
||
==[[w:C_Sharp|C#]], [[w:Java|Java]]<ref>Для соответствия правилам оформления кода Java метод следует переименовать в <code>gcd</code> и перенести <code>{</code> в конец предыдущей строки</ref>== |
|||
==[[w:C_Sharp|C#]]== |
|||
Вместо <code>long</code> можно использовать и другие целочисленные типы — <code>byte</code>, <code>int</code> и т. д. |
|||
Вместо <code>T</code> следует подставить любой целочисленный тип — <code>byte</code>, <code>long</code>, <code>UInt32</code> и т. д. (C#, в отличие от C++ и Java, не поддерживает [[w:Утиная типизация|«утиную» типизацию]] для обобщённых типов, а также не предоставляет ни отдельного интерфейса для числовых типов, ни средств создания псевдонимов типов наподобие <code>typedef</code> в C/C++). |
|||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="csharp"> |
<source lang="csharp"> |
||
static |
static long GCD (long a, long b) |
||
{ |
{ |
||
while (b != 0) |
while (b != 0) |
||
b = a % (a = b); |
b = a % (a = b); |
||
return |
return a < 0 ? -a : a; |
||
} |
} |
||
</source> |
</source> |
||
Строка 148: | Строка 147: | ||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
<source lang="csharp"> |
<source lang="csharp"> |
||
static |
static long GCD (long a, long b) |
||
{ |
{ |
||
return b == 0 ? |
return b == 0 ? (a < 0 ? -a : a) : GCD(b, a % b); |
||
} |
} |
||
</source> |
</source> |
||
Строка 186: | Строка 185: | ||
</source> |
</source> |
||
⚫ | |||
==[[w:Java|Java]]== |
|||
Тип <code>IntType</code> определён как: |
|||
⚫ | |||
<source lang=" |
<source lang="pascal"> |
||
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип } |
|||
public static <T> T gcd (T a, T b) { |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
return Math.abs(a); |
|||
} |
|||
</source> |
</source> |
||
⚫ | |||
Также допустимы функции, аналогичные написанным выше на C, например так: |
|||
<source lang="java"> |
|||
public static <T> gcd (T a, T b) { |
|||
while (b != 0) |
|||
b ^= a ^= b ^= a %= b; |
|||
return Math.abs(a); |
|||
} |
|||
</source> |
|||
''*короткая запись работает не корректно. Например при начальных значениях 34 и 9 уже на следующем шаге значения получаются 43 и 0...'' |
|||
Деление с остатком, рекурсия: |
|||
<source lang="java"> |
|||
public static <T> T gcd (T a, T b) { |
|||
return b == 0 ? Math.abs(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"> |
<source lang="pascal"> |
||
function GCD (a, b: |
function GCD (a, b: IntType): IntType; |
||
begin |
begin |
||
while a * b <> 0 do |
while a * b <> 0 do |
||
Строка 234: | Строка 206: | ||
Более быстрый алгоритм: |
Более быстрый алгоритм: |
||
<source lang="pascal"> |
<source lang="pascal"> |
||
function GCD (a, b: |
function GCD (a, b: IntType): IntType; |
||
var c: |
var c: IntType; |
||
begin |
begin |
||
while b > 0 do |
while b > 0 do |
||
Строка 249: | Строка 221: | ||
Деление с остатком, рекурсия: |
Деление с остатком, рекурсия: |
||
<source lang="pascal"> |
<source lang="pascal"> |
||
function GCD (a, b: |
function GCD (a, b: IntType): IntType; |
||
begin |
begin |
||
if b = 0 then |
if b = 0 then |
||
Строка 267: | Строка 239: | ||
==[[w:PHP|PHP]]== |
==[[w:PHP|PHP]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="php"> |
<source lang="php"> |
||
function gcd ($a, $b) { |
function gcd ($a, $b) { |
||
Строка 303: | Строка 275: | ||
==[[w:Python|Python]]== |
==[[w:Python|Python]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="python"> |
<source lang="python"> |
||
def gcd (a, b): |
def gcd (a, b): |
||
Строка 318: | Строка 290: | ||
==[[:Ruby|Ruby]]== |
==[[:Ruby|Ruby]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="ruby"> |
<source lang="ruby"> |
||
def gcd (a, b) |
def gcd (a, b) |
||
Строка 334: | Строка 306: | ||
</source> |
</source> |
||
Вычитание, |
Вычитание, цикл: |
||
<source lang="ruby"> |
<source lang="ruby"> |
||
def gcd (a, b) |
def gcd (a, b) |
||
Строка 349: | Строка 321: | ||
==[[w:Rust (язык программирования)|Rust]]== |
==[[w:Rust (язык программирования)|Rust]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source lang="rust"> |
<source lang="rust"> |
||
extern crate num; |
extern crate num; |
||
use self::num::FromPrimitive; |
use self::num::FromPrimitive; |
||
use std:: |
use std::ops::Rem; |
||
use std::ops::RemAssign; |
|||
pub fn gcd < |
pub fn gcd <IntType> (mut a: IntType, mut b: IntType) -> IntType |
||
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> { |
|||
let zero = FromPrimitive::from_u32(0u32).unwrap(); // Обобщённая константа 0 |
|||
a %= b; |
|||
let mut c: IntType; |
|||
mem::swap(&mut a, &mut b); |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
a |
a |
||
Строка 367: | Строка 342: | ||
</source> |
</source> |
||
Вычитание, |
Вычитание, цикл: |
||
<source lang="rust"> |
<source lang="rust"> |
||
use std::ops::SubAssign; |
use std::ops::SubAssign; |
||
Строка 411: | Строка 386: | ||
==[[w:Глагол (язык программирования)|Глагол]]== |
==[[w:Глагол (язык программирования)|Глагол]]== |
||
Деление с остатком, |
Деление с остатком, цикл: |
||
<source> |
<source> |
||
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ; |
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ; |
||
Строка 427: | Строка 402: | ||
==Программируемые микрокалькуляторы «Электроника»== |
==Программируемые микрокалькуляторы «Электроника»== |
||
Деление с остатком, |
Деление с остатком, цикл. |
||
Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека. |
|||
Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе). |
Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе). |
||
===МК-52 / 61 / 152 / 161=== |
===МК-52 / 61 / 152 / 161 / 163 / 1152=== |
||
<source> |
<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. × |
Версия от 14:38, 11 мая 2017
Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных языках программирования.
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
Деление с остатком, цикл:
GW-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%)
QuickBasic версий < 4.0, Turbo Basic
DEF FNGCD% (A%, B%)
DO WHILE B% <> 0
A% = A% MOD B%
SWAP A%, B%
LOOP
FNGCD% = ABS(A%)
END DEF
PowerBASIC, QBASIC, QuickBasic версий ≥ 4.0, Visual Basic
Function GCD (a As Integer, b As Integer) As Integer
Do While a <> 0 And b <> 0
If a > b Then
a = a Mod b
Else
b = b Mod a
End If
Loop
GCD = Abs(a + b) ' Для VB.NET следует заменить эту строку на Return Math.Abs(a + b)
End Function
Деление с остатком, рекурсия:
PowerBASIC, QBASIC, QuickBasic версий ≥ 4.0, Visual Basic
Function GCD (a As Integer, b As Integer) As Integer
If b = 0 Then
GCD = Abs(a) ' Для VB.NET следует заменить эту строку на Return Math.Abs(a)
Else
GCD = GCD(b, a Mod b) ' Для VB.NET следует заменить GCD = на Return
End If
End Function
C/C++
C: Тип IntType
должен быть задан как:
typedef int IntType; /* Вместо int можно подставить любой другой целочисленный тип */
C++: Любую из нижеприведённых функций (включая abs
) следует предварить строкой:
template < typename IntType >
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:
IntType abs (IntType value) {
return (value < 0) ? -value : value;
}
Деление с остатком, цикл:
IntType gcd (IntType a, IntType b) {
IntType c;
while (b) {
c = a % b;
a = b;
b = c;
}
return abs(a);
}
Более короткое решение:
IntType gcd (IntType a, IntType b) {
while (b)
b ^= a ^= b ^= a %= b;
return abs(a);
}
Деление с остатком, рекурсия:
IntType gcd (IntType a, IntType b) {
return (b == 0) ? abs(a) : gcd(b, a % b);
}
Вычитание, цикл:
IntType gcd (IntType a, IntType b) {
a = abs(a);
b = abs(b);
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}
return a;
}
C#, Java[1]
Вместо long
можно использовать и другие целочисленные типы — byte
, int
и т. д.
Деление с остатком, цикл:
static long GCD (long a, long b)
{
while (b != 0)
b = a % (a = b);
return a < 0 ? -a : a;
}
Деление с остатком, рекурсия:
static long GCD (long a, long b)
{
return b == 0 ? (a < 0 ? -a : 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 ;
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)
Pascal
Тип IntType
определён как:
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
Деление с остатком, цикл:
function GCD (a, b: IntType): IntType;
begin
while a * b <> 0 do
if a > b then
a := a mod b
else
b := b mod a;
GCD := Abs(a + b)
end;
Более быстрый алгоритм:
function GCD (a, b: IntType): IntType;
var c: IntType;
begin
while b > 0 do
begin
c := a mod b;
a := b;
b := c
end;
GCD := Abs(a)
end;
Деление с остатком, рекурсия:
function GCD (a, b: IntType): IntType;
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) {
while ($a <> 0 && $b <> 0) {
if ($a > $b)
$a = $a % $b;
else
$b = $b % $a;
}
return abs($a + $b);
}
echo gcd(5, 3);
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)
w: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, b):
while b:
a, b = b, a % b
return abs(a)
Деление с остатком, рекурсия:
def gcd (a, b):
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
Вычитание, цикл:
def gcd (a, b)
a = a.abs
b = b.abs
if a > b
a -= b
else
b -= a
end while a != b
a
end
Rust
Деление с остатком, цикл:
extern crate num;
use self::num::FromPrimitive;
use std::ops::Rem;
pub fn gcd <IntType> (mut a: IntType, mut b: IntType) -> IntType
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> {
let zero = FromPrimitive::from_u32(0u32).unwrap(); // Обобщённая константа 0
let mut c: IntType;
while b != zero {
c = a % b;
a = b;
b = c;
}
a
}
Вычитание, цикл:
use std::ops::SubAssign;
pub fn gcd <T: Copy + PartialOrd + SubAssign> (mut a: T, mut b: T) -> T {
while a != b {
if a > b {
a -= b;
} else {
b -= a;
}
}
a
}
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: ЦЕЛ): ЦЕЛ;
УКАЗ
ПОКА (a # 0) И (b # 0) ВЫП
ЕСЛИ a < b ТО
b := b ОСТАТОК a
ИНАЧЕ
a := a ОСТАТОК b
КОН
КОН;
ВОЗВРАТ МОДУЛЬ(a + b)
КОН НОД;
Программируемые микрокалькуляторы «Электроника»
Деление с остатком, цикл.
Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека.
Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе).
МК-52 / 61 / 152 / 161 / 163 / 1152
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. С/П
См. также
- ↑ Для соответствия правилам оформления кода Java метод следует переименовать в
gcd
и перенести{
в конец предыдущей строки