Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями
Содержимое удалено Содержимое добавлено
м Мелкие исправления; метод подходит и для Java |
Добавлена рекурсивная реализация на Python |
||
Строка 1:
{{wikipedia |Бинарный алгоритм вычисления НОД}}
=Реализации=
==[[w:C (язык программирования)|С]]==
Строка 164 ⟶ 166 :
return $v*$g;
}
</source>
==[[w:Python|Python]]==
Рекурсия:
<source lang="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)
</source>
| |||