Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями
Содержимое удалено Содержимое добавлено
FeelUs (обсуждение | вклад) Javascript |
|||
Строка 62: | Строка 62: | ||
<source lang="pascal"> |
<source lang="pascal"> |
||
function GCD(a, b: |
function GCD (a, b: Integer): Integer; |
||
begin |
begin |
||
if a = 0 then |
if a = 0 then |
||
GCD:= b |
GCD := b |
||
else if b = 0 then |
else if b = 0 then |
||
GCD:= a |
GCD := a |
||
else if a = b then |
else if a = b then |
||
GCD:= a |
GCD := a |
||
else if (a = 1) or (b =1) then |
else if (a = 1) or (b = 1) then |
||
GCD:= 1 |
GCD := 1 |
||
else if (a |
else if (a and 1) = 0 then |
||
if (b and 1) = 0 then |
|||
GCD := GCD(a shr 1, b shr 1) shl 1 |
|||
else |
|||
GCD := GCD(a shr 1, b) |
|||
⚫ | |||
⚫ | |||
if (b and 1) = 0 then |
|||
⚫ | |||
GCD:= GCD( |
GCD := GCD(a, b shr 1) |
||
else |
|||
⚫ | |||
end; |
end; |
||
</source> |
</source> |
Версия от 21:46, 10 мая 2017
С
unsigned int gcd(unsigned int u, unsigned int v)
{
int shift;
/* GCD(0,x) := x */
if (u == 0 || v == 0)
return u | v;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
while ((v & 1) == 0) /* Loop X */
v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u < v) {
v -= u;
} else {
unsigned int diff = u - v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u << shift;
}
C#
long GCD(long a, long b)
{
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, (long)Math.Abs(a - b));
}
Pascal
function GCD (a, b: Integer): Integer;
begin
if a = 0 then
GCD := b
else if b = 0 then
GCD := a
else if a = b then
GCD := a
else if (a = 1) or (b = 1) then
GCD := 1
else if (a and 1) = 0 then
if (b and 1) = 0 then
GCD := GCD(a shr 1, b shr 1) shl 1
else
GCD := GCD(a shr 1, b)
else
if (b and 1) = 0 then
GCD := GCD(a, b shr 1)
else
GCD := GCD(b, Abs(a - b))
end;
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;
}
}
Perl
sub nod
{
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);
}