@Slava191

Как научиться решать задачи по программированию с большими числами?

Например, дана задача
/**
 * Count ones in a segment
 * Given two numbers: 'left' and 'right' (1 <= 'left' <= 'right' <= 200000000000000) return sum of all '1' occurencies in binary representations of numbers between 'left' and 'right' (including both)

    Example:
    countOnes 4 7 should return 8, because:
    4(dec) = 100(bin), which adds 1 to the result.
    5(dec) = 101(bin), which adds 2 to the result.
    6(dec) = 110(bin), which adds 2 to the result.
    7(dec) = 111(bin), which adds 3 to the result.
    So finally result equals 8.
    WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!
 */


Как эволюционировать от таких решений

function countOnes(left, right) {
  let sum = 0
  const CountBits = (n) => Number(n).toString(2).split('')
                                    .reduce((acc, v) => v==='1' ? ++acc : acc, 0)

  for(let n = left; n<=right; n++){
    sum+=CountBits(n)
  }

  return sum
}


К вот таким

function countOnesSingle(n) {
    let result = 0;
    while (n > 0) {

      let k = Math.floor(Math.log2(n));

      result += Math.pow(2, k - 1) * k + 1;

      n = n - Math.pow(2, k);

      result += n;
    }
    return result;
  }
  
  function countOnes(left, right) {
    return countOnesSingle(right) - countOnesSingle(left - 1);
  }


Очевидно, что простым нарешиванием делу не помочь.

p.s.

Нужны именно такие задачи, на большие числа. С задачи по типу "проверить правильно ли решено судоку" или "поделить грядки по какому-то замысловатому алгоритму" или "просчитать шахматную комбинацию" проблем нет. Но когда в дело вступют большие числа начинается фигня...
  • Вопрос задан
  • 446 просмотров
Пригласить эксперта
Ответы на вопрос 2
gbg
@gbg
Любые ответы на любые вопросы
Учить математику, в частности, алгебру и теорию чисел. Фамилия задачника - Бухштаб
Ответ написан
@res2001
Developer, ex-admin
Использовать готовые библиотеки для работы с большими числами для используемого ЯП.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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