Я хотел бы найти наибольший общий делитель с использованием JavaScript.
Кто-нибудь сделал это раньше и хочет поделиться?
Ответ 1
Вот рекурсивное решение.
var gcd = function(a, b) {
if ( ! b) {
return a;
}
return gcd(b, a % b);
};
Наш базовый случай, когда b равен 0. В этом случае мы возвращаем a.
Когда мы рекурсируем, мы заменяем входные аргументы, но мы передаем остаток a / b в качестве второго аргумента.
Ответ 2
Взято из Википедии.
Рекурсивный:
function gcd_rec(a, b) {
if (b) {
return gcd_rec(b, a % b);
} else {
return Math.abs(a);
}
}
Итерационный:
function gcd(a,b) {
a = Math.abs(a);
b = Math.abs(b);
if (b > a) {var temp = a; a = b; b = temp;}
while (true) {
if (b == 0) return a;
a %= b;
if (a == 0) return b;
b %= a;
}
}
РЕДАКТИРОВАН за каждый комментарий пользователя
Ответ 3
function egcd(a, b) {
if (a == 0)
return b;
while (b != 0) {
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}