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

Перейти к навигации Перейти к поиску
м
Мелкие исправления; метод подходит и для Java
(Улучшена разметка, оптимизирован код)
м (Мелкие исправления; метод подходит и для Java)
</source>
 
==[[w:C_Sharp|C#]], [[w:Java|Java]]<ref>Для соответствия правилам оформления кода Java метод следует переименовать в <code>gcd</code> и перенести <code>{</code> в конец предыдущей строки</ref>==
==[[w:C_Sharp|C#]]==
Рекурсия:
<source lang="csharp">
static long GCD (long a, long b)
{
if (a == 0)
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, (long)Math.Abs(a > b ? a - b) : b - a); // …если b — нечётное, то НОД(a, b) = НОД(b, |a - b|)
}
</source>
74

правки

Навигация