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

==[[w:C (язык программирования)|С]]==

Цикл:

typedef unsigned int Integer; /* Вместо unsigned int можно подставить любой другой целочисленный тип */

 

return a << shift;

}

 

==[[w:C_Sharp|C#]], [[w:Java|Java]]==

Рекурсия:

static long gcd (long a, long b) {

if (a == 0)

: gcd (b, a > b ? a - b : b - a); // …если b — нечётное, то НОД(a, b) = НОД(b, |a - b|)

}

 

==[[w:JavaScript|JavaScript]]==

Без рекурсии:

function GCD (a, b) { // НОД двух целых чисел

var factor = 1;

}

}

 

==[[w:Паскаль (язык программирования)|Pascal]]==

Рекурсия:

type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }

 

GCD := GCD(a shr 1, b shr 1) shl 1 { НОД(a, b) = 2 * НОД(a / 2, b / 2) }

end;

 

==[[w:Perl|Perl]]==

Без рекурсии:

sub gcd

{

return $v*$g;

}

 

==[[w:Python|Python]]==

Рекурсия:

# Возвращает True, если число нечётно, False иначе

def is_odd (number):

else: # …если b — чётное, то…

return gcd(a >> 1, b >> 1) << 1 # НОД(a, b) = 2 * НОД(a / 2, b / 2)

 

==[[w:Ruby|Ruby]]==

Рекурсия:

def gcd(m, n)

return n if m == 0

gcd(n, (m - n).abs)

end

 

==[[w:Scala|Scala]]==

<!-- Добавил Рыжий Лис red-fox0@mail.ru -->

Рекурсия:

def GCD(a:BigInt, b:BigInt):BigInt = {

if (a == 0) return b;

return GCD(b, (a - b).abs);

}

 

{{BookCat}}