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

Question

[Torento20345]

Есть задача на получение всех кратных чисел 3 и 5.
Можно ее как-то эффективней решить?
https://jsfiddle.net/7pa4Luzn/

Answer 1

[Adamos]

Если нужно определить кратность - то берем учебник Математика, 6 класс.
Глава Признаки кратности 3, 5 и 9 с минимумом вычислений.
Если же нужно заполнить массив - то потери времени на его заполнение, да в жабоскрипте, на порядки превышают стоимость этой простенькой проверки.
Может ускорить (а может и замедлить) этот процесс замена в цикле ++i на прибавление того числа, которое действительно надо прибавить для получения следующего кратного - оно циклично повторяется: [3, 2, 1, 3, 1, 2, 3]. Проверка уберется, но вычислений, на самом деле, только прибавится. Зато без ветвления и пустых циклов.

Comments

[WbICHA]

но вычислений, на самом деле, только прибавится.

С чего это вдруг?
Во-первых, количество итераций уменьшится в несколько раз.
Во-вторых, уберутся проверки на кратность 3 и 5. И остаток от деления останется лишь один, для высчитывания следующего индекса порядка. То есть останется лишь одна проверка на размер текущей суммы.

Answer 2

[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)

Answer 3

[Alexandroppolus]

Как вариант - cмержить последовательности 3n и 5n
https://jsfiddle.net/0rhsL1ba/

не знаю, насколько это поможет здесь, но будь числа покрупнее, точно бы ускорилось

Answer 4

[Сергей Соколов]

Цикл последовательности = 3 * 5 = 15

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

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

Comments

[WbICHA]

Проблема этого решения в том, что оно не позволяет доставать промежуточные значения, a именно в этом и заключается задача.
Если же несколько изменить это решение, чтобы запоминать числа, то в итоге получится решение Adamos.)

[Сергей Соколов]

WbICHA, какие ещё промежуточные?

получение всех кратных чисел

Я предлагаю что-то типа

function getSequence(n) {
  const length = 15; // или вычислить 3 * 5
  const block = [0, 3, 5, 6, 9, 10, 12,]; // или вычислить один раз
  const fit = n / length;
  const fullBlocks = Math.floor(fit);
  const result = [];

  // кирпичи целиком
  for (let i = 0; i < fullBlocks; i++)
    result.push(...block.map((v) => v + length * i));

  // последний кирпич кусочками по одному
  for (let i = 0; i < block.length; i++) {
    const value = block[i] + length * fullBlocks;
    if (n < value) break;
    result.push(value);
  }

  return result;
}

[WbICHA]

Сергей Соколов,

for (let i = 0; i < fullBlocks; i++)
    result.push(...block.map((v) => v + length * i));

Это очевидное решение, НО тс спрашивает про более эффективный алгоритм, а это решение, как минимум в рамках жс, намного медленнее аналогов выше.

То есть моя претензия не к тому, что это не решить, а к тому, что это не решить эффективно.