Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎BASIC: Оптимизации
Усовершенствования алгоритма для разных языков
Строка 27:
 
==[[w:Бейсик|BASIC]]==
===[[w:Dartmouth_BASIC|Оригинальный (Dartmouth BASIC]])===
Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):
<source lang="basic">
10 INPUTPRINT "Two integer numbers", A, B;
20 INPUT A, B
30 PRINT "GCD("; A; ", "; B,") = ";
3040 LET A = ABS(A): LET B = ABS(B)
4050 IF B = 0 THEN GOTO 90120
60 LET B = ABS(B)
50 IF A >= B THEN LET A = A - B: GOTO 50
6070 IF A =< 0B THEN LET A = B: GOTO 90
7080 LET BA = BA - AB: IF B >= A THEN GOTO 70
8090 IF BA <>= 0 THEN LET A = B: GOTO 50120
100 LET B = B - A: IF B >= A THEN GOTO 100
90 PRINT A
110 IF B > 0 THEN GOTO 80
100 END
120 PRINT A
130 END
</source>
 
===[[w:GW-BASIC|GW-BASIC]] и совместимые диалекты===
Цикл, деление с остатком либо вычитание (при указанных заменах в коде).:
<source lang="basic">
10 INPUT "Two integer numbers", A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
30 A% = ABS(A%):WHILE B% =<> ABS(B%)0
40 WHILEA% B= A% >MOD 0B%
50 IF A% = 0 THEN A% MOD= B%: 'ДляB% вычитания= заменить0: наELSE WHILE AB% >= B%: A% =MOD A% - B%: WEND
60 WEND
60 IF A% = 0 THEN A% = B%: GOTO 90
70 PRINT ABS(A%)
70 B% = B% MOD A% 'Для вычитания заменить на WHILE B% >= A%: B% = B% - A%: WEND
80 WEND
90 PRINT A%
</source>
 
===[[w:QuickBasic|QuickBasic]] версий < 4.0, [[w:Turbo Basic|Turbo Basic]]===
Цикл, деление с остатком либо вычитание (при указанных заменах в коде).:
<source lang="basic">
DEF FNGCD%(A%, B%)
ADO UNTIL B% = ABS(A%)0
B% = ABS(B%)
DO WHILE B% > 0
A% = A% MOD B%
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'DO UNTIL A% < B%
' A% = A% - B%
'LOOP
IF A% = 0 THEN
FNGCD% = ABS(B%)
EXIT DEF
END IF
B% = B% MOD A%
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'DO 'Перед входом в этот цикл 0 < A% < B%, поэтому проверка B% < A% вынесена в постусловие
' B% = B% - A%
'LOOP UNTIL B% < A%
LOOP
FNGCD% = ABS(A%)
END DEF
</source>
Строка 85 ⟶ 76 :
В следующих примерах используется тип <code>Long</code> (длинное целое); вместо него можно применять также тип <code>Integer</code> (стандартное целое).
 
Цикл, деление с остатком либо вычитание (при указанных заменах в коде):
<source lang="vb">
Function GCD(a As Long, b As Long) As Long
Do Until b = 0
a = Abs(a)
b = Abs(b)
Do While b > 0
a = a Mod b
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'Do Until a < b
' a = a - b
'Loop
If a = 0 Then
GCD = b
Строка 101 ⟶ 86 :
End If
b = b Mod a
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'Do 'Перед входом в этот цикл 0 < a < b, поэтому проверка b < a вынесена в постусловие
' b = b - a
'Loop Until b < a
Loop
GCD = a
Строка 113 ⟶ 94 :
<source lang="vb">
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
</source>
 
===[[w:VB.NET|VBVisual Basic .NET]]===
В следующих примерах используется тип <code>Long</code> (длинное целое); вместо него можно применять любые другие целочисленные типы платформы [[w:NET_Framework|.NET]].
 
Цикл, деление с остатком либо вычитание (при указанных заменах в коде):
<source lang="vb">
Shared Function GCD(ByVal a As Long, ByVal b As Long) As Long
Do Until b = 0
a = Math.Abs(a)
b = Math.Abs(b)
Do While b > 0
a = a Mod b
If a = 0 Then Return Math.Abs(b)
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'Do Until a < b
' a -= b
'Loop
If a = 0 Then Return b
b = b Mod a
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'Do 'Перед входом в этот цикл 0 < a < b, поэтому проверка b < a вынесена в постусловие
' b -= a
'Loop Until b < a
Loop
Return Math.Abs(a)
End Function
</source>
 
Рекурсия, деление с остатком либо вычитание (при указанных заменах в коде):
<source lang="vb">
Shared 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 или более поздняя версия
If b = 0 Then Return Math.Abs(a)
Return GCD(b, a Mod b)
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'If a >= b Then Return GCD(a, a - b)
'Return GCD(b, b - a)
End Function
</source>
 
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Тип <code>IntTypeInteger</code> должен быть задан как:
<source lang="c">typedef int IntTypeInteger; /* Вместо int можно подставить любой другой целочисленный тип */</source>
 
'''C++:''' Любую из нижеприведённых функций (включая <code>abs</code>) следует предварить строкой:
<source lang="cpp">template < typename IntType Integer></source>
Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:
<source lang="c">
IntTypeInteger abs (IntTypeInteger value) {
return (value < 0) ? -value : value;
}
</source>
 
Деление с остатком, цикл:
 
<source lang="c">
IntTypeInteger gcd (IntTypeInteger a, IntTypeInteger b) {
for (Integer c; b; ) {
IntType c;
c = a % while (b) {;
c a = a % b;
a b = bc;
}
b = c;
return abs(a);
}
}
return abs(a);
</source>
 
Без использования дополнительной переменной:
<source lang="c">
Integer gcd (Integer a, Integer b) {
while (b)
b ^= a ^= b ^= a %= b;
return abs(a);
}
</source>
 
Без использования дополнительной переменной и с наименьшим числом сравнений и присваиваний:
Более короткое решение:
<source lang="c">
IntTypeInteger gcd (IntTypeInteger a, IntTypeInteger b) {
while if (b!a)
return abs(b);
b ^= a ^= b ^= a %= b;
if (!b)
return abs(a);
for ( ; ; )
if (!(a %= b))
return abs(b);
else if (!(b %= a))
return abs(a);
}
</source>
Строка 194 ⟶ 176 :
Деление с остатком, рекурсия:
<source lang="c">
IntTypeInteger gcd (IntTypeInteger a, IntTypeInteger b) {
return (!b == 0) ? abs(a) : gcd(b, a % b);
}
</source>
Строка 201 ⟶ 183 :
Вычитание, цикл:
<source lang="c">
IntTypeInteger gcd (IntTypeInteger a, IntTypeInteger b) {
a = abs(a);
b = abs(b);
while (a != b) {
if while (a >= b)
a -= b;
if (!a)
else
return b;
b -= a;
do {
b -= a;
} while (b >= a);
}
return a;
Строка 214 ⟶ 199 :
</source>
 
==[[w:C_Sharp|C#]], [[w:Java|Java]]==
==[[w:C_Sharp|C#]], [[w:Java|Java]]<ref>Для соответствия правилам оформления кода Java метод следует переименовать в <code>gcd</code> и перенести <code>{</code> в конец предыдущей строки</ref>==
Приведён код для C#. Для Java следует заменить <code>Abs</code> на <code>abs</code> и, для соответствия правилам оформления кода, переименовать функции в <code>gcd</code> и перенести <code>{</code> в конец предыдущей строки.
 
Вместо <code>long</code> можно использовать и другие целочисленные типы — <code>byte</code>, <code>int</code> и т. д.
 
Деление с остатком, цикл:
<source lang="csharp">
static long GCD (long a, long b)
{
while (b != 0)
b = a % (a = b);
return Math.Abs(a < 0 ? -a : a);
}
</source>
 
<source lang="csharp">
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);
if ((b %= a) == 0)
return Math.Abs(a);
}
}
</source>
Строка 231 ⟶ 234 :
static long GCD (long a, long b)
{
return b == 0 ? Math.Abs(a < 0 ? -a : a) : GCD(b, a % b);
}
</source>
Строка 260 ⟶ 263 :
Тип <code>IntType</code> определён как:
<source lang="go">
type IntTypeInteger = int // Вместо int можно подставить любой другой целочисленный тип
</source>
 
Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа:
<source lang="go">
func IntAbs(value IntTypeInteger) IntTypeInteger {
if value < 0 {
return -value
Строка 275 ⟶ 278 :
Деление с остатком, цикл:
<source lang="go">
func GCD(a, b IntTypeInteger) IntTypeInteger {
for b != 0 {
a %= b
Строка 287 ⟶ 290 :
</source>
 
Деление с остатком, рекурсия:
Вычитание, цикл:
<source lang="go">
func GCD(a, b IntTypeInteger) IntTypeInteger {
if b == 0 {
a = IntAbs(a)
b = return IntAbs(ba)
for b != 0 {
for a >= b {
a -= b
}
if a == 0 {
return b
}
for b >= a {
b -= a
}
}
return GCD(b, a % b)
}
</source>
Строка 318 ⟶ 311 :
 
==[[w:Паскаль (язык программирования)|Pascal]]==
Тип <code>IntTypeTInteger</code> определён как:
<source lang="pascal">
type IntTypeTInteger = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
</source>
 
Деление с остатком, цикл:
<source lang="pascal">
function GCD (a, b: IntTypeTInteger): IntTypeTInteger;
begin
while a * b <> 0 do
if a > b then
a := a mod b
else
b := b mod a;
GCD := Abs(a + b)
end;
</source>
 
Более быстрый алгоритм:
<source lang="pascal">
function GCD (a, b: IntType): IntType;
var c: IntType;
begin
while b <> 0 do
begin
c a := a mod b;
if a := b;0 then
begin
b := c
a := endb;
GCD b := Abs(a)0
end
else
b := b mod a
end;
GCD := Abs(a)
end;
</source>
Строка 353 ⟶ 337 :
Деление с остатком, рекурсия:
<source lang="pascal">
function GCD (a, b: IntTypeTInteger): IntTypeTInteger;
begin
if b = 0 then
GCD := Abs(a)
else
GCD := GCD(b, a mod b)
end;
</source>
Строка 366 ⟶ 350 :
<source lang="perl">
sub gcd {
return $_[0] != 0 ? gcd ( ( $_[1] % $_[0] ), $_[0] ) : $_[1];
}
</source>
Строка 374 ⟶ 358 :
<source lang="php">
function gcd ($a, $b) {
while if ($a <> 0 && $b <>=== 0) {
return abs($b);
if ($a > $b)
if ($b === 0)
$a = $a % $b;
return abs($a)
else
for ( ; ; )
$b = $b % $a;
if (($a %= $b) === 0)
}
return abs($a + $b);
else if (($b %= $a) === 0)
return abs($a);
}
echo gcd(5, 3);
Строка 409 ⟶ 395 :
Деление с остатком, цикл:
<source lang="python">
def gcd (a: int, b: int) -> int:
while b:
a, b = b, a % b
return abs(a)
</source>
 
Деление с остатком, рекурсия:
<source lang="python">
def gcd (a: int, b: int) -> int:
return abs(a) if b == 0 else gcd(b, a % b)
</source>
 
Строка 424 ⟶ 410 :
Деление с остатком, цикл:
<source lang="ruby">
def gcd (a, b)
a, b = b, a % b until b.zero?
a.abs
end
</source>
Строка 432 ⟶ 418 :
Деление с остатком, рекурсия:
<source lang="ruby">
def gcd (a, b)
return a.abs if b.zero?
gcd(b, a % b)
end
</source>
 
Вычитание, цикл:
<source lang="ruby">
def gcd (a, b)
a = a.abs
b = b.abs
if a > b
a -= b
else
b -= a
end while a != b
a
end
</source>
Строка 463 ⟶ 435 :
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
a
}
</source>
Строка 480 ⟶ 452 :
 
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
a
}
</source>
Строка 502 ⟶ 474 :
<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
}
 
Строка 522 ⟶ 494 :
ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
ПОКА (a # 0) И (b # 0) ВЫП
a := a ОСТАТОК b;
ЕСЛИ a < b ТО
ЕСЛИ a = 0 ТО
b := b ОСТАТОК a
ИНАЧЕ a := b;
b := 0
a := a ОСТАТОК b
ИНАЧЕ
b := b ОСТАТОК a
КОН
КОН;
ВОЗВРАТ МОДУЛЬ(a + b)
КОН НОД;
</source>
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Алгоритм_Евклида