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

(Добавлена рекурсивная реализация на Python)
else: # …если b — чётное, то…
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>
 
3

правки