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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Добавлена рекурсивная реализация на Python
Строка 195: Строка 195:
else: # …если b — чётное, то…
else: # …если b — чётное, то…
return gcd(a >> 1, b >> 1) << 1 # НОД(a, b) = 2 * НОД(a / 2, b / 2)
return gcd(a >> 1, b >> 1) << 1 # НОД(a, b) = 2 * НОД(a / 2, b / 2)
</source>

==[[w:Ruby|Ruby]]==
Рекурсия:
<source lang="ruby">
def gcd(m, n)
if m == 0
return n
elsif n == 0
return m
elsif m == n
return m
elsif m == 1 || n == 1
return 1
elsif m.even? && n.even?
return gcd(m/2, n/2)
elsif m.even? && n.odd?
return gcd(m/2, n)
elsif m.odd? && n.even?
return (m, n/2)
else
if n > m
return gcd((n - m) / 2, m)
else
return Binary_GCD((m - n) / 2, n)
end
end
end
</source>
</source>



Версия от 14:01, 4 июня 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#, Java[1]

Рекурсия:

static 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, a > b ? a - b : b - a); // …если 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;
}

Python

Рекурсия:

# Возвращает True, если число нечётно, False иначе
def is_odd (number):
    return (number & 1) == 1

# Возвращает наибольший общий делитель целых чисел a и b
def gcd (a, b):
    if a == 0:
        return b                            # НОД(0, b) = b
    elif b == 0:
        return a                            # НОД(a, 0) = a
    elif a == b:
        return a                            # НОД(a, a) = a
    elif a == 1 or b == 1:
        return 1                            # НОД(1, b) = НОД(a, 1) = 1
    elif is_odd(a):                         # Если а — нечётное, то…
        if is_odd(b):                       # …если b — нечётное, то…
            return gcd(b, abs(a - b))       # НОД(a, b) = НОД(b, |a - b|)
        else:                               # …если b — чётное, то…
            return gcd(a, b >> 1)           # НОД(a, b) = НОД(a, b / 2)
    else:                                   # Если a — чётное…
        if is_odd(b):                       # …если b — нечётное, то…
            return gcd(a >> 1, b)           # НОД(a, b) = НОД(a / 2, b)
        else:                               # …если b — чётное, то…
            return gcd(a >> 1, b >> 1) << 1 # НОД(a, b) = 2 * НОД(a / 2, b / 2)

Ruby

Рекурсия:

def gcd(m, n)
  if m == 0
    return n
  elsif n == 0
    return m
  elsif m == n
    return m
  elsif m == 1 || n == 1
    return 1
  elsif m.even? && n.even?
    return gcd(m/2, n/2)
  elsif m.even? && n.odd?
    return gcd(m/2, n)
  elsif m.odd? && n.even?
    return (m, n/2)
  else
    if n > m
      return gcd((n - m) / 2, m)
    else
      return Binary_GCD((m - n) / 2, n)
    end
  end
end

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);
}
  1. Для соответствия правилам оформления кода Java метод следует переименовать в gcd и перенести { в конец предыдущей строки