Советы по JavaScript
Как найти наибольший общий делитель в JavaScript
Обзор различных методов вычисления НОД в JavaScript
Проблема сегодня связана с математикой. В частности, речь идет о нахождении наибольшего общего делителя двух натуральных чисел. В математике наибольший общий делитель двух целых чисел a и b, которые оба не равны нулю, обозначается GCD(a,b) и является наибольшим натуральным числом, на которое можно разделить оба числа.
Задача: наибольший общий делитель
ссылка на ката
Найдите наибольший общий делитель двух натуральных чисел. Целые числа могут быть большими, поэтому вам нужно найти умное решение.
Входные данные x и y всегда больше или равны 1, поэтому наибольший общий делитель всегда будет целым числом, которое также больше или равно 1.
Решение: алгоритм Евклида
Наибольший общий делитель можно вычислить, в принципе, путем определения простой факторизации двух заданных чисел и умножения общих делителей, рассматриваемых только один раз, на их наименьший показатель степени.
Этот метод удобен только для очень малых чисел: разложение числа на простые множители обычно занимает слишком много времени.
Алгоритм Евклида обеспечивает гораздо более эффективный метод. В Википедии есть хорошая страница, посвященная алгоритму Евклида, поэтому я рекомендую ее прочитать.
Таким образом, есть 3 разных способа получить наибольший общий делитель. Первый метод используется Евклидом и использует вычитание.
function gcd(a, b) {
while (a !== b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
Второй метод использует умножение.
function gcd(a, b) {
while (b !== 0) {
const t = b;
b = a % b;
a = t;
}
return a;
}
Наконец, третий метод — это рекурсивная функция.
const gcd = (x, y) => (y === 0 ? x : gcd(y, x % y));
Но есть и другие методы.
Метод наименьших абсолютных остатков
Метод наименьших абсолютных остатков — это вариант алгоритма Евклида, который используется для нахождения НОД двух целых чисел. Он основан на наблюдении, что НОД двух целых чисел равен НОД абсолютных значений их остатков. Этот метод особенно полезен, когда входные целые числа могут быть отрицательными, так как он гарантирует, что НОД всегда будет положительным целым числом.
function gcd(a, b) {
if (a === 0 || b === 0) {
return Math.max(a, b);
}
let r = a % b;
while (r) {
a = b;
b = r;
r = a % b;
}
return Math.abs(b);
}
Двоичный алгоритм GCD
Двоичный алгоритм НОД — это эффективный вариант алгоритма Евклида, который использует побитовые операции и рекурсивные вызовы для нахождения НОД двух целых чисел. Он имеет временную сложность O (log n), где n — большее из двух входных целых чисел, что в некоторых случаях делает его быстрее, чем другие алгоритмы GCD. Однако он требует больше памяти из-за использования рекурсивных вызовов и не всегда может быть наиболее подходящим алгоритмом для использования.
function gcd(a, b) {
if (a === 0 || b === 0) {
return Math.max(a, b);
}
if (a === b) {
return a;
}
if (a % 2 === 0 && b % 2 === 0) {
return 2 * gcd(a / 2, b / 2);
}
if (a % 2 === 0) {
return gcd(a / 2, b);
}
if (b % 2 === 0) {
return gcd(a, b / 2);
}
return gcd(Math.abs(a - b), Math.min(a, b));
}
Спасибо за прочтение! Оставайтесь с нами, чтобы узнать больше.
Не пропустите мою следующую статью — подпишитесь на мой средний список адресов электронной почты
Первоначально опубликовано на https://blog.stranianelli.com 30 декабря 2022 г.
Больше контента на PlainEnglish.io.
Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord.
