@Torento20345

Какой алгоритм вычисления кратности чисел более эффективен?

Есть задача на получение всех кратных чисел 3 и 5.
Можно ее как-то эффективней решить?
https://jsfiddle.net/7pa4Luzn/
  • Вопрос задан
  • 770 просмотров
Решения вопроса 4
Adamos
@Adamos
Если нужно определить кратность - то берем учебник Математика, 6 класс.
Глава Признаки кратности 3, 5 и 9 с минимумом вычислений.
Если же нужно заполнить массив - то потери времени на его заполнение, да в жабоскрипте, на порядки превышают стоимость этой простенькой проверки.
Может ускорить (а может и замедлить) этот процесс замена в цикле ++i на прибавление того числа, которое действительно надо прибавить для получения следующего кратного - оно циклично повторяется: [3, 2, 1, 3, 1, 2, 3]. Проверка уберется, но вычислений, на самом деле, только прибавится. Зато без ветвления и пустых циклов.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Судя по названию функции (sum) вам надо найти сумму чисел. Это делается в одно действие без циклов вообще.

Если бы были нужны только числа делящееся на 3, то их сумма - f(n, 3)=3*floor(n/3)(floor(n/3)+1)/2. Эта формула получается вынесением 3 за скобки в сумме и дальше применением формулы армфметической прогрессии.

Чтобы взять сумму делящихся на 3 или 5 надо взять сумму делящихся на 3, прибавить сумму делящихся на 5 и вычесть сумму делящихся на 15. Потому что делящиеся на 15 были подсчитанны 2 раза в первых слагаемых. Т.е. ответ - f(n,3)+f(n,5)-f(n,15)
Ответ написан
Комментировать
Alexandroppolus
@Alexandroppolus
кодир
Как вариант - cмержить последовательности 3n и 5n
https://jsfiddle.net/0rhsL1ba/

не знаю, насколько это поможет здесь, но будь числа покрупнее, точно бы ускорилось
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега JavaScript
♬♬
Цикл последовательности = 3 * 5 = 15

Можно рассчитать или захардкодить повторяющийся блок, и копировать его, добавляя i * 15, где i = 0, 1, 2, ..

В последнем блоке придется искать, на каком элементе остановиться.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы