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

Добавлено описание алгоритма, добавлены реализации на JavaScript, переработаны реализации для Rust и ПМК, мелкие исправления
(Усовершенствования алгоритма для разных языков)
(Добавлено описание алгоритма, добавлены реализации на JavaScript, переработаны реализации для Rust и ПМК, мелкие исправления)
Реализации [[w:алгоритм Евклида|алгоритма Евклида]] для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных [[w:язык программирования|языках программирования]].
 
=Описание=
'''Классический алгоритм Евклида''' применяется к паре неотрицательных целых чисел. Пока ни одно из чисел в паре не равно нулю, из большего числа вычитается меньшее; вычитаемое и полученная разность формируют новую пару. Действие повторяется, пока один из элементов пары не обратится в 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))
 
Оба алгоритма обобщаются на ноль и отрицательные значения. При этом следует иметь ввиду:
* Помимо положительных общих делителей у чисел имеются и отрицательные. Однако наибольший общий делитель по определению не может быть отрицательным (очевидно, что любое положительное число больше любого отрицательного). Таким образом НОД двух чисел равен НОДу их модулей.
* Если одно из чисел в паре равно нулю, а другое — нет, то их НОД равен модулю ненулевого числа.
* НОД пары нулей может рассматриваться, как неопределённое значение или бесконечность, а может [https://math.stackexchange.com/questions/495119/what-is-gcd0-0 приниматься равным нулю]. Приведённые реализации в основном придерживаются последнего подхода (технически он реализуется проще).
* Подавляющее большинство языков программирования представляют отрицательные целые числа в так называемом [[w:Дополнительный_код|дополнительном коде]], при этом у наименьшего отрицательного значения типа отсутствует парное положительное значение (например наименьшее значение 16-битного знакового целого — −32768, а наибольшее — 32767). Следовательно вычисление НОД с применением наименьшего значения знакового типа может вызывать переполнение и давать неверные результаты.
 
Как правило, языки программирования включают функцию или оператор нахождения остатка от деления двух чисел, поэтому соответствующие реализации используют именно быстрый алгоритм Евклида. Алгоритм, построенный на вычитании, имеет смысл использовать на тех системах, где встроенная операция нахождения остатка отсутствует и её невыгодно эмулировать, например, через деление и взятие целой части.
 
=Реализации=
 
==[[w:Бейсик|BASIC]]==
===Классический===
===Оригинальный (Dartmouth BASIC)===
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):
<source lang="basic">
</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 для приложений]]===
В следующих примерах используется тип <code>Long</code> (длинное целое); вместо него можно применять также тип <code>Integer</code> (стандартное целое).
 
 
Деление с остатком, цикл:
 
<source lang="c">
Integer gcd (Integer a, Integer 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);
}
}
</source>
 
==[[w:Go|Go]]==
Тип <code>IntTypeInteger</code> определён как:
<source lang="go">
type Integer = int // Вместо int можно подставить любой другой целочисленный тип
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)
</source>
 
==[[w:JavaScript|JavaScript]], [[w:ECMAScript|ECMAScript]]==
Деление с остатком, цикл:
<source lang="js">
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);
}
</source>
 
Деление с остатком, рекурсия:
<source lang="js">
const gcd = (a, b) => b === 0 ? Math.abs(a) : gcd(b, a % b); // ECMAScript версий ≥ 6.0
</source>
 
return abs($a);
}
echo gcd(5, 3);
</source>
 
Деление с остатком, цикл:
<source lang="rust">
extern crateuse num::Zero;
use std::ops::{RemAssign, Sub};
 
fn gcd <Integer> (a: Integer, b: Integer) -> Integer
use self::num::FromPrimitive;
where Integer: Zero + PartialOrd + Sub<Output = Integer> + RemAssign + Copy
use std::ops::Rem;
{
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;
pub fn gcd <IntType> (mut a: IntType, mut b: IntType) -> IntType
if _a.is_zero() {
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> {
result = _b;
let zero = FromPrimitive::from_u32(0u32).unwrap(); // Обобщённая константа 0
break;
let mut c: IntType;
};
while b != zero {
c _b %= a % b_a;
if _b.is_zero() {
a = b;
b result = c_a;
break;
};
};
};
// `result` берётся по модулю
if result < Integer::zero() {
Integer::zero() - result
} else {
result
}
a
}
</source>
 
Деление с остатком, рекурсия:
Вычитание, цикл:
<source lang="rust">
use stdnum::ops::SubAssignZero;
use std::ops::{Rem, Sub};
 
pub fn gcd <Integer> (a: Integer, b: Integer) -> Integer
 
pubwhere fn gcd <TInteger: CopyZero + PartialOrd + SubAssign>Sub<Output (mut= a:Integer> T,+ mutRem<Output b: T)= -Integer> T+ {Copy
{
while a != b {
if a > b.is_zero() {
// Возвращаемое значение берётся по модулю
a -= b;
if a < Integer::zero() {
Integer::zero() - a
} else {
b -= a;
}
} else {
gcd(b, a % b)
}
a
}
</source>
 
==Программируемые микрокалькуляторы «Электроника»==
Использование: <первое число> → регистр В↑Y, <второе число> → регистр X, В/О, С/П (НОД на индикаторе).
 
===Б3-21, МК-61 / 52 / 152 / 16146 / 16364, / 1152МС-1103===
Деление с остаткомВычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека X и Y.
<source>
00. Fx≠0Px≠0 01. 13 02. 03. В↑ Px≥0 04. FВxF1 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. ×
10. − 11. Fx=0/−/ 12. 02 13. + Px=0 14. K|x|Peⁱˣ 15. С/П
20. С/П
</source>
 
Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.
<source>
00. Fx≠0 01. 13 01. Fx≠0 02. 12 03. Fx<0 04. 09 05. FВx/−/ 06. FВx 07. /−/ 08. − 09. FВx
10. БП 11. 00 Fx=0 12. FВx02 13. + 14. С/П
</source>
 
===Б3-21, МК-4661 / 52 / 152 / 161 / 64,163 МС-1103/ 1152===
ВычитаниеДеление с остатком, цикл. Корректно обрабатываются любые целые неотрицательные числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека X и Y.
<source>
00. Px≠0Fx≠0 01. 13 02. 03. Px≥0В↑ 04. F1 FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. ×
10. − 11. /−/ Fx=0 12. 02 13. Px=0+ 14. PeⁱˣK|x| 15. С/П
20. С/П
</source>
 
74

правки