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

Содержимое удалено Содержимое добавлено
Добавлены реализации и примеры их использования на Rust
Нет описания правки
Строка 3:
==[[w:Язык_ассемблера|Assembler]]==
===ARM===
Вычитание, без рекурсиицикл:
<source lang="arm">
loop CMP Ri, Rj ; проверка условий NE (i != j), GT (i > j) и LT (i < j);
Строка 12:
 
===Z80===
Вычитание, без рекурсиицикл:
<source lang="z80">
GCD_DEHL: ; CALL Inputs: HL,DE; Output: DE
Строка 26:
 
==[[w:Бейсик|BASIC]]==
Деление с остатком, без рекурсиицикл:
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты===
<source lang="basic">
Строка 76:
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип T<code>IntType</code> должен быть задан как:
<source lang="c">typedef int TIntType; /* Вместо int можно подставить любой другой целочисленный тип */</source>
Вместо <code>…</code> нужно подставить любой целочисленный тип (<code>int</code>, <code>unsigned</code>, <code>short</code> и т. д.)
 
'''C++:''' любуюЛюбую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой:
<source lang="cpp">template < typename TIntType ></source>
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:
<source lang="c">
TIntType abs (TIntType value) {
return (value < (T)0) ? -value : value;
}
</source>
 
Деление с остатком, без рекурсиицикл:
<source lang="c">
TIntType gcd (TIntType a, TIntType b) {
TIntType c;
while (b) {
c = a % b;
Строка 104 ⟶ 103 :
Более короткое решение:
<source lang="c">
TIntType gcd (TIntType a, TIntType b) {
while (b)
b ^= a ^= b ^= a %= b;
Строка 113 ⟶ 112 :
Деление с остатком, рекурсия:
<source lang="c">
TIntType gcd (TIntType a, TIntType b) {
return (b == 0) ? abs(a) : gcd(b, a % b);
}
</source>
 
Вычитание, без рекурсиицикл:
<source lang="c">
TIntType gcd (TIntType a, TIntType b) {
a = abs(a);
b = abs(b);
Строка 133 ⟶ 132 :
</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">
static Tlong GCD (Tlong a, Tlong b)
{
while (b != 0)
b = a % (a = b);
return Math.Abs(a) < 0 ? -a : a;
}
</source>
Строка 148 ⟶ 147 :
Деление с остатком, рекурсия:
<source lang="csharp">
static Tlong GCD (Tlong a, Tlong b)
{
return b == 0 ? Math.Abs(a < 0 ? -a : a) : GCD(b, a % b);
}
</source>
Строка 186 ⟶ 185 :
</source>
 
==[[w:Паскаль (язык программирования)|Pascal]]==
==[[w:Java|Java]]==
Тип <code>IntType</code> определён как:
Деление с остатком, без рекурсии:
<source lang="javapascal">
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
public static <T> T gcd (T a, T b) {
while (b != 0) {
T c = a % b;
a = b;
b = c;
}
return Math.abs(a);
}
</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>
 
==[[w:Паскаль (язык программирования)|Pascal]]==
Тип T определён как <code>type T = …;</code>, вместо <code>…</code> следует подставить любой целочисленный тип (<code>Integer</code>, <code>Byte</code>, <code>LongInt</code> и т. д.)
 
Деление с остатком, без рекурсии:
<source lang="pascal">
function GCD (a, b: TIntType): TIntType;
begin
while a * b <> 0 do
Строка 234 ⟶ 206 :
Более быстрый алгоритм:
<source lang="pascal">
function GCD (a, b: TIntType): TIntType;
var c: TIntType;
begin
while b > 0 do
Строка 249 ⟶ 221 :
Деление с остатком, рекурсия:
<source lang="pascal">
function GCD (a, b: TIntType): TIntType;
begin
if b = 0 then
Строка 267 ⟶ 239 :
 
==[[w:PHP|PHP]]==
Деление с остатком, без рекурсиицикл:
<source lang="php">
function gcd ($a, $b) {
Строка 303 ⟶ 275 :
 
==[[w:Python|Python]]==
Деление с остатком, без рекурсиицикл:
<source lang="python">
def gcd (a, b):
Строка 318 ⟶ 290 :
 
==[[:Ruby|Ruby]]==
Деление с остатком, без рекурсиицикл:
<source lang="ruby">
def gcd (a, b)
Строка 334 ⟶ 306 :
</source>
 
Вычитание, без рекурсиицикл:
<source lang="ruby">
def gcd (a, b)
Строка 349 ⟶ 321 :
 
==[[w:Rust (язык программирования)|Rust]]==
Деление с остатком, без рекурсиицикл:
<source lang="rust">
extern crate num;
 
use self::num::FromPrimitive;
use std::memops::Rem;
use std::ops::RemAssign;
 
 
pub fn gcd <T: Copy + FromPrimitive + PartialEq + RemAssignIntType> (mut a: TIntType, mut b: TIntType) -> T {IntType
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> {
whilelet bzero != FromPrimitive::from_u32(0u32).unwrap(); {// Обобщённая константа 0
a %= b;
let mut c: IntType;
mem::swap(&mut a, &mut b);
while (b != 0)zero {
T c = a % b;
a = b;
b = c;
}
a
Строка 367 ⟶ 342 :
</source>
 
Вычитание, без рекурсиицикл:
<source lang="rust">
use std::ops::SubAssign;
Строка 411 ⟶ 386 :
 
==[[w:Глагол (язык программирования)|Глагол]]==
Деление с остатком, без рекурсиицикл:
<source>
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
Строка 427 ⟶ 402 :
 
==Программируемые микрокалькуляторы «Электроника»==
Деление с остатком, без рекурсиицикл.

Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека.
 
Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе).
===МК-52 / 61 / 152 / 161 / 163 / 1152===
<source>
00. Fx≠0 01. 13 02. ↔ 03. В↑ 04. FВx 05. ÷ 06. FВx 07. ↔ 08. K[x] 09. ×