Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями

м
<source> -> <syntaxhighlight> (phab:T237267)
м (<source> -> <syntaxhighlight> (phab:T237267))
==[[w:C (язык программирования)|С]]==
Цикл:
<sourcesyntaxhighlight lang="c">
typedef unsigned int Integer; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
 
return a << shift;
}
</syntaxhighlight>
</source>
 
==[[w:C_Sharp|C#]], [[w:Java|Java]]==
Рекурсия:
<sourcesyntaxhighlight lang="csharp">
static long gcd (long a, long b) {
if (a == 0)
: gcd (b, a > b ? a - b : b - a); // …если b — нечётное, то НОД(a, b) = НОД(b, |a - b|)
}
</syntaxhighlight>
</source>
 
==[[w:JavaScript|JavaScript]]==
Без рекурсии:
<sourcesyntaxhighlight lang="javascript">
function GCD (a, b) { // НОД двух целых чисел
var factor = 1;
}
}
</syntaxhighlight>
</source>
 
==[[w:Паскаль (язык программирования)|Pascal]]==
Рекурсия:
<sourcesyntaxhighlight lang="pascal">
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
 
GCD := GCD(a shr 1, b shr 1) shl 1 { НОД(a, b) = 2 * НОД(a / 2, b / 2) }
end;
</syntaxhighlight>
</source>
 
==[[w:Perl|Perl]]==
Без рекурсии:
<sourcesyntaxhighlight lang="perl">
sub gcd
{
return $v*$g;
}
</syntaxhighlight>
</source>
 
==[[w:Python|Python]]==
Рекурсия:
<sourcesyntaxhighlight lang="python">
# Возвращает True, если число нечётно, False иначе
def is_odd (number):
else: # …если b — чётное, то…
return gcd(a >> 1, b >> 1) << 1 # НОД(a, b) = 2 * НОД(a / 2, b / 2)
</syntaxhighlight>
</source>
 
==[[w:Ruby|Ruby]]==
Рекурсия:
<sourcesyntaxhighlight lang="ruby">
def gcd(m, n)
return n if m == 0
gcd(n, (m - n).abs)
end
</syntaxhighlight>
</source>
 
==[[w:Scala|Scala]]==
<!-- Добавил Рыжий Лис red-fox0@mail.ru -->
Рекурсия:
<sourcesyntaxhighlight lang="scala">
def GCD(a:BigInt, b:BigInt):BigInt = {
if (a == 0) return b;
return GCD(b, (a - b).abs);
}
</syntaxhighlight>
</source>
 
{{BookCat}}
583

правки