Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Улучшена разметка, оптимизирован код
Строка 1:
{{wikipedia |Бинарный алгоритм вычисления НОД}}
 
==[[w:C (язык программирования)|С]]==
== С ==
Без рекурсии:
 
<source lang="c">
typedef unsigned int IntType; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
unsigned int gcd(unsigned int u, unsigned int v)
 
{
IntType gcd (IntType a, IntType b) {
int shift;
int shift;
 
/* GCDНОД(0, x) := x */
if (ua == 0 || vb == 0)
return ua | vb;
 
/* Вычисление shift = lg K, где K — наибольшая степень 2, на которую делятся без остатка a и b. */
/* Let shift := lg K, where K is the greatest power of 2
for (shift = 0; dividing((a both| ub) and& v.1) */== 0; ++shift) {
for (shift = 0;a ((u | v) &>>= 1) == 0; ++shift) {
ub >>= 1;
v >>= 1;}
}
 
while ((ua & 1) == 0)
u a >>= 1;
 
/* FromНачиная hereотсюда on,a uвсегда is always oddнечётно. */
do {
while ((vb & 1) == 0) /* LoopЦикл по X */
v b >>= 1;
 
/* NowТеперь ua andи vb areнечётны, bothпоэтому odd,их soразность (diff(u, v) is evenчётна.
LetВычисление ua = min(ua, vb), vb = diff(u,a v- b) / 2. */
if (ua < vb) {
vb -= ua;
} else {
unsigned intIntType diff = ua - vb;
ua = vb;
vb = diff;
}
vb >>= 1;
} while (vb != 0);
 
return ua << shift;
}
</source>
 
== [[w:C_Sharp|C# ]]==
Рекурсия:
 
<source lang="csharp">
long GCD (long a, long b)
{
if (a == 0) return b;
return b; // НОД(0, b) = b
if (b == 0) return a;
if (ab == b0) return a;
return a; // НОД(a, 0) = a
if (a == 1 || b == 1) return 1;
if ((a % 2 == 0) && (b % 2 == 0)) return 2 * GCD(a / 2, b / 2);
if (( return a; % 2 == 0) && (b % 2 != 0)) return GCD(a // 2НОД(a, ba); = a
if ((a % 2 !== 0)1 &&|| (b % 2 == 0)) return GCD(a, b / 21);
return GCD1; // НОД(b1, (longb)Math.Abs = НОД(a, - b1)); = 1
if (a & 1 == 0) // Если а — чётное, то…
return (b & 1 == 0)
? GCD(a >> 1, b >> 1) << 1 // …если b — чётное, то НОД(a, b) = 2 * НОД(a / 2, b / 2)
: GCD(a >> 1, b); // …если b — нечётное, то НОД(a, b) = НОД(a / 2, b)
else // Если a — нечётное, то…
return (b & 1 == 0)
? GCD(a, b >> 1) // …если b — чётное, то НОД(a, b) = НОД(a, b / 2)
: GCD(b, (long)Math.Abs(a - b)); // …если b — нечётное, то НОД(a, b) = НОД(b, |a - b|)
}
</source>
 
==[[w:JavaScript|JavaScript]]==
== Pascal ==
Без рекурсии:
<source lang="javascript">
function GCD (a, b) { // НОД двух целых чисел
var factor = 1;
while (true) {
// НОД(0, b) = b; НОД(a, 0) = a; НОД(a, a) = a;
if (a == b)
if (a == 0)
throw 'GCD(0, 0)'
else
return factor * a;
if (a == 0)
return factor * b;
if (b == 0)
return factor * a;
// НОД(1, b) = 1; НОД(a, 1) = 1;
if (a == 1 || b == 1)
return factor;
//Если a и b чётные, то НОД(a, b) = 2 * НОД(a / 2, b / 2);
if (!(a & 1) && !(b & 1)){
factor <<= 1;
a >>= 1;
b >>= 1;
}
// Если a чётное, b нечётное, то НОД(a, b) = НОД(a / 2, b);
else if (!(a & 1))
a >>= 1;
// Если b чётное, a нечётное, то НОД(a, b) = НОД(a, b / 2);
else if (!(b & 1))
b >>= 1;
// Если a и b нечётные и b > a, то НОД(a, b) = НОД((b - a) / 2, a);
else if (b > a)
b = (b - a) >> 1;
// Если a и b нечётные и b < a, то НОД(a, b) = НОД((a - b) / 2, b);
else
a = (a - b) >> 1;
}
}
</source>
 
==[[w:Паскаль (язык программирования)|Pascal]]==
Рекурсия:
<source lang="pascal">
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }
function GCD (a, b: Integer): Integer;
 
function GCD (a, b: IntType): IntType;
begin
if a = 0 then
GCD := b { НОД(0, b) = b }
else if b = 0 then
GCD := a { НОД(a, 0) = a }
else if a = b then
GCD := a { НОД(a, a) = a }
else if (a = 1) or (b = 1) then
GCD := 1 { НОД(1, b) = НОД(a, 1) = 1 }
GCD := 1
else if Odd(a) then { Если а — нечётное, то… }
else if (a and 1) = 0 then
if Odd(b) then { …если b — нечётное, то… }
if (b and 1) = 0 then
GCD := GCD(b, Abs(a shr- 1b)) { НОД(a, b) shr= 1)НОД(b, shl|a - b|) 1}
else { …если b — чётное, то… }
else
GCD := GCD(a, b shr 1) { НОД(a, b) = НОД(a, b / 2) }
else { Если a — чётное… }
else
if Odd(b) then { …если b — нечётное, то… }
if (b and 1) = 0 then
GCD := GCD(a shr 1, b) shr 1 { НОД(a, b) = НОД(a / 2, b) }
else { …если b — чётное, то… }
else
GCD := GCD(a shr 1, b shr 1) shl 1 { НОД(a, Absb) = 2 * НОД(a -/ 2, b / 2)) }
end;
</source>
 
== Javascript [[w:Perl|Perl]]==
Без рекурсии:
 
<source lang="javascript">
function GCD(m,n){ // НОД двух чисел
var factor = 1;
while(true){
//НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
if(m==n)
if(m==0) throw 'GCD(0,0)'
else return factor*m;
if(m==0) return factor*n;
if(n==0) return factor*m;
//НОД(1, n) = 1; НОД(m, 1) = 1;
if(m==1 || n==1) return factor;
//Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
if(!(m&1) && !(n&1)){
factor<<=1;
m>>=1;
n>>=1;
}
//Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
else if(!(m&1)) m>>=1;
//Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
else if(!(n&1)) n>>=1;
//Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
else if(n>m) n = (n-m)>>1;
//Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);
else m = (m-n)>>1;
}
}
</source>
 
== Perl ==
 
<source lang="perl">
sub nodgcd
{
return $_[0] if $_[1] == 0;
Строка 147 ⟶ 166 :
</source>
 
== [[w:Scala |Scala]]==
<!-- Добавил Рыжий Лис red-fox0@mail.ru -->
Рекурсия:
<source lang="scala">
def GCD(a:BigInt, b:BigInt):BigInt = {
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (a == 1 || b == 1) return 1;
if ((a % 2 == 0) && (b % 2 == 0)) return 2 * GCD(a / 2, b / 2);
if ((a % 2 == 0) && (b % 2 != 0)) return GCD(a / 2, b);
if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2);
return GCD(b, (a - b).abs);
}
</source>
 
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Бинарный_алгоритм_вычисления_НОД