Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями
Содержимое удалено Содержимое добавлено
Улучшена разметка, оптимизирован код |
|||
Строка 1: | Строка 1: | ||
{{wikipedia |Бинарный алгоритм вычисления НОД}} |
{{wikipedia |Бинарный алгоритм вычисления НОД}} |
||
==[[w:C (язык программирования)|С]]== |
|||
== С == |
|||
Без рекурсии: |
|||
<source lang="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; |
|||
/* НОД(0, x) = x */ |
|||
if (a == 0 || b == 0) |
|||
return |
return a | b; |
||
/* Вычисление shift = lg K, где K — наибольшая степень 2, на которую делятся без остатка a и b. */ |
|||
/* Let shift := lg K, where K is the greatest power of 2 |
|||
for (shift = 0; ((a | b) & 1) == 0; ++shift) { |
|||
a >>= 1; |
|||
b >>= 1; |
|||
} |
|||
} |
|||
while ((a & 1) == 0) |
|||
a >>= 1; |
|||
/* |
/* Начиная отсюда a всегда нечётно. */ |
||
do { |
do { |
||
while (( |
while ((b & 1) == 0) /* Цикл по X */ |
||
b >>= 1; |
|||
/* |
/* Теперь a и b нечётны, поэтому их разность (diff) чётна. |
||
Вычисление a = min(a, b), b = (a - b) / 2. */ |
|||
if ( |
if (a < b) { |
||
b -= a; |
|||
} else { |
} else { |
||
IntType diff = a - b; |
|||
a = b; |
|||
b = diff; |
|||
} |
} |
||
b >>= 1; |
|||
} while ( |
} while (b != 0); |
||
return |
return a << shift; |
||
} |
} |
||
</source> |
</source> |
||
== |
==[[w:C_Sharp|C#]]== |
||
Рекурсия: |
|||
<source lang="csharp"> |
<source lang="csharp"> |
||
long GCD(long a, long b) |
long GCD (long a, long b) |
||
{ |
{ |
||
if (a == 0) |
if (a == 0) |
||
return b; // НОД(0, b) = b |
|||
if (b == 0) return a; |
|||
if ( |
if (b == 0) |
||
return a; // НОД(a, 0) = a |
|||
if (a == 1 || b == 1) return 1; |
|||
if |
if (a == b) |
||
return a; // НОД(a, a) = a |
|||
if |
if (a == 1 || b == 1) |
||
return |
return 1; // НОД(1, b) = НОД(a, 1) = 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> |
</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"> |
<source lang="pascal"> |
||
type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип } |
|||
function GCD (a, b: Integer): Integer; |
|||
function GCD (a, b: IntType): IntType; |
|||
begin |
begin |
||
if a = 0 then |
if a = 0 then |
||
GCD := b |
GCD := b { НОД(0, b) = b } |
||
else if b = 0 then |
else if b = 0 then |
||
GCD := a |
GCD := a { НОД(a, 0) = a } |
||
else if a = b then |
else if a = b then |
||
GCD := a |
GCD := a { НОД(a, a) = a } |
||
else if (a = 1) or (b = 1) then |
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(a |
GCD := GCD(b, Abs(a - b)) { НОД(a, b) = НОД(b, |a - b|) } |
||
else { …если b — чётное, то… } |
|||
else |
|||
GCD := GCD(a shr 1, b) |
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, b |
GCD := GCD(a shr 1, b) { НОД(a, b) = НОД(a / 2, b) } |
||
else { …если b — чётное, то… } |
|||
else |
|||
GCD := GCD(b, |
GCD := GCD(a shr 1, b shr 1) shl 1 { НОД(a, b) = 2 * НОД(a / 2, b / 2) } |
||
end; |
end; |
||
</source> |
</source> |
||
== |
==[[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"> |
<source lang="perl"> |
||
sub |
sub gcd |
||
{ |
{ |
||
return $_[0] if $_[1] == 0; |
return $_[0] if $_[1] == 0; |
||
Строка 147: | Строка 166: | ||
</source> |
</source> |
||
== |
==[[w:Scala|Scala]]== |
||
<!-- Добавил Рыжий Лис red-fox0@mail.ru --> |
<!-- Добавил Рыжий Лис red-fox0@mail.ru --> |
||
Рекурсия: |
|||
<source lang="scala"> |
<source lang="scala"> |
||
def GCD(a:BigInt, b:BigInt):BigInt = { |
|||
if (a == 0) return b; |
if (a == 0) return b; |
||
if (b == 0) return a; |
if (b == 0) return a; |
||
if (a == b) return a; |
if (a == b) return a; |
||
if (a == 1 || b == 1) return 1; |
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 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 / 2, b); |
||
if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2); |
if ((a % 2 != 0) && (b % 2 == 0)) return GCD(a, b / 2); |
||
return GCD(b, (a-b).abs); |
return GCD(b, (a - b).abs); |
||
} |
|||
</source> |
</source> |
||
Версия от 08:40, 11 мая 2017
С
Без рекурсии:
typedef unsigned int IntType; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
IntType gcd (IntType a, IntType b) {
int shift;
/* НОД(0, x) = x */
if (a == 0 || b == 0)
return a | b;
/* Вычисление shift = lg K, где K — наибольшая степень 2, на которую делятся без остатка a и b. */
for (shift = 0; ((a | b) & 1) == 0; ++shift) {
a >>= 1;
b >>= 1;
}
while ((a & 1) == 0)
a >>= 1;
/* Начиная отсюда a всегда нечётно. */
do {
while ((b & 1) == 0) /* Цикл по X */
b >>= 1;
/* Теперь a и b нечётны, поэтому их разность (diff) чётна.
Вычисление a = min(a, b), b = (a - b) / 2. */
if (a < b) {
b -= a;
} else {
IntType diff = a - b;
a = b;
b = diff;
}
b >>= 1;
} while (b != 0);
return a << shift;
}
C#
Рекурсия:
long GCD (long a, long b)
{
if (a == 0)
return b; // НОД(0, b) = b
if (b == 0)
return a; // НОД(a, 0) = a
if (a == b)
return a; // НОД(a, a) = a
if (a == 1 || b == 1)
return 1; // НОД(1, b) = НОД(a, 1) = 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|)
}
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;
}
}
Pascal
Рекурсия:
type IntType = 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 }
else if Odd(a) then { Если а — нечётное, то… }
if Odd(b) then { …если b — нечётное, то… }
GCD := GCD(b, Abs(a - b)) { НОД(a, b) = НОД(b, |a - b|) }
else { …если b — чётное, то… }
GCD := GCD(a, b shr 1) { НОД(a, b) = НОД(a, b / 2) }
else { Если a — чётное… }
if Odd(b) then { …если b — нечётное, то… }
GCD := GCD(a shr 1, b) { НОД(a, b) = НОД(a / 2, b) }
else { …если b — чётное, то… }
GCD := GCD(a shr 1, b shr 1) shl 1 { НОД(a, b) = 2 * НОД(a / 2, b / 2) }
end;
Perl
Без рекурсии:
sub gcd
{
return $_[0] if $_[1] == 0;
return $_[1] if $_[0] == 0;
($u, $v)=@_; $g=1;$t=100;
while (1)
{
if ($u%2==1 || $v%2==1) {last;};
$u>>=1; ##(right shift)
$v>>=1;
$g<<=1; ## (left shift)
}
while ($u > 0)
{
if ($u%2==0 && $u>0) {$u = $u>>1;}
elsif ($v%2==0 && $v>0) {$v = $v>>1;}
else
{
$t = abs (($u-$v)/2);
if ($u < $v) {$v = $t;} else {$u = $t;}
}
}
return $v*$g;
}
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);
}