Function nod(x,y) {
let count=1;
for (let i=1; i<x || i<y; i++) {
if (x%i==0 && y%i==0) {
count=i;
} else {
continue;
}
}
return count;
}
JavaScript
Ищу НОД (js), как можно ускорить цикл? з. ы. Я только учусь=)
ускорить цикл можно переносом кода на YoptaScript. Подробнее на yopta.space
Достаточно продолжать цикл только до sqrt(min(x, y)):
function nod(x, y) {
let res = 1;
if (x > y) { [x, y] = [y, x]; }
for (int i = 1; i * i <= x; ++i) {
if (x % i) { continue; } // x не делится на i
if (y % (x / i) == 0) { return x / i; } // подошёл больший делитель
if (y % i == 0) { res = i; } // подошёл меньший делитель.
}
return res;
}
Всегда x <= y.
Если x делится на i, имеем 2 делителя: i и x / i, причём x / i >= i. Если y делится на x / i - сразу возвращаем x / i, т. к. это гарантировано НОД.
Но, разумеется, алгоритм Евклида быстрее и короче:
function nod(x, y) {
while (x) { [x, y] = [y % x, x]; }
return y;
}
function nod(x, y) {
let res = 1;
if (x > y) { [x, y] = [y, x]; }
for (int i = 1; i * i <= x; ++i) {
if (x % i) { continue; } // x не делится на i
if (y % (x / i) == 0) { return x / i; } // подошёл больший делитель
if (y % i == 0) { res = i; } // подошёл меньший делитель.
}
return res;
}
Всегда x <= y.
Если x делится на i, имеем 2 делителя: i и x / i, причём x / i >= i. Если y делится на x / i - сразу возвращаем x / i, т. к. это гарантировано НОД.
Но, разумеется, алгоритм Евклида быстрее и короче:
function nod(x, y) {
while (x) { [x, y] = [y % x, x]; }
return y;
}
Ускорить цикл можно, если не импровизировать и не использовать перебор, а воспользоваться традиционным алгоритмом Эвклида.
Aibek .
Благодарю за Эвклида, задачку удалось ускорить с его помощью, но можно ли как-то ускорить код с перебором?
Конкретно этот цикл можно записать так:
function nod(x, y) {
if (x > y) [x, y] = [y, x];
// Гарантирует, что x меньше.
let div = y / x;
if ((div | 0) == div) return x;
// Если и так делится нацело, сразу возвращает меньшее число без перебора
let count = 1, stop = x / 2;
// Точно не делится, значит делитель как минимум будет меньше или равен x / 2
// количество итераций сократится вдвое.
for (let i = 1; i <= stop; i++) {
if (x % i + y % i == 0) {
count = i;
}
}
return count;
}
_________
i<x || i<y; — выкинул две проверки, сразу можно определить меньшее и перебрать до него.
else { continue } — бессмысленно, т. к. основной код и так заключен в if, а после него нет другого кода.
Можно еще подумать, для двух случайных чисел наибольший делитель чаще оказывается ближке к маленьким числам или большим, при необходимости начинать цикл сверху вниз.
function nod(x, y) {
if (x > y) [x, y] = [y, x];
// Гарантирует, что x меньше.
let div = y / x;
if ((div | 0) == div) return x;
// Если и так делится нацело, сразу возвращает меньшее число без перебора
let count = 1, stop = x / 2;
// Точно не делится, значит делитель как минимум будет меньше или равен x / 2
// количество итераций сократится вдвое.
for (let i = 1; i <= stop; i++) {
if (x % i + y % i == 0) {
count = i;
}
}
return count;
}
_________
i<x || i<y; — выкинул две проверки, сразу можно определить меньшее и перебрать до него.
else { continue } — бессмысленно, т. к. основной код и так заключен в if, а после него нет другого кода.
Можно еще подумать, для двух случайных чисел наибольший делитель чаще оказывается ближке к маленьким числам или большим, при необходимости начинать цикл сверху вниз.
Aibek .
Благодарю за ответ =) Буду экспериментировать.
Похожие вопросы
- Подскажите сайт (ы) где показаны что добавили в js нового, чтобы список нововведений обновлялся
- Помогите определиться с выбором нового языка (JS(TS) vs Java)
- Js фреймворки, что полезного можно для себя найти?
- В чем цель фреймворков js web?
- [HTML/CSS/JS] Как сохранять изменённые в .js данные оффлайн-сервера локально?
- Почему jQuery методы популярнее js методов при общении с ДоМ?
- ПОЧЕМУ JS ТАКОЙ НЕПОНЯТНЫЙ???
- вопрос по JS. " простой ()";
- Порядок изучени JavaScripta. Путь к Node.js. Нужен совет по обучению от программистов
- Почему иногда в вакансиях пишут "знания JavaScript или JQuery"? По сути JQuery - лишь библиотека для JS.