Сделать цикл и код более эффективным для обработки больших чисел с помощью циклов - PullRequest
Новая
       29

Сделать цикл и код более эффективным для обработки больших чисел с помощью циклов

0 голосов
/ 18 мая 2018

это задание на Codewars, другими словами, домашнее задание.:) Я должен написать функцию, которая возвращает количество чисел от 1 до n (включительно), которое можно представить как разность двух идеальных квадратов.Например, 20 = 6² - 4² и 21 = 5² - 2².Многие числа могут быть записаны таким образом, но не все.

Я написал функцию, она хорошо работает, но должна уметь обрабатывать n значений вплоть до 45000.В основном мой код падает, когда он анализирует числа в порядке тысяч.Чтобы сделать код более эффективным, я попытался изменить начальный цикл с n до 0, а не с 0 до n.Я пытался разделить n на два, пока он не станет достаточно маленьким, а затем умножить окончательный результат на 2 раза снова, но не получилось.Я также использовал цикл while, но потом понял, что просто не знаю, как решить эту проблему, и после 3-х дней бессмысленных попыток решить ее с помощью грубой силы, я прошу о помощи, поскольку я нехочу просто отказаться от этого.Это мой код 

function countSquareable(n){
  var y = []
  var c = []

  for (var i = 0; i <= n; i++) { // all numbers powered in range
  y.push(Math.pow(i,2))
  }

for(i = 0; i < y.length; i++) {
    c.push(y.map(a => y[i]-a)) //  all subtractions' combos

}

var d = c.toString().split(",").sort(function(a, b){return a-b}).filter(function(a) {return a>0 && a<=n}) // only the combos I need in the range

var a = [], b = [], prev; // remove duplicates
d.sort();
    for ( var i = 0; i < d.length; i++ ) {
        if ( d[i] !== prev ) {
            a.push(d[i]);
            b.push(1);
        } else {
            b[b.length-1]++;
        }
        prev = d[i];
    }

return console.log(a.length) // end result



};
countSquareable(500)

countSquareable(4) // should return 3 and it works
countSquareable(5) // should return 4 and it works
countSquareable(40) // should return 30 and it works
countSquareable(45000) // should return 33750 but crashes
countSquareable(6427), // should return 4820 but crashes

Как сделать код НАМНОГО более эффективным для решения проблемы?Ката здесь .спасибо !!

1 Ответ

0 голосов
/ 18 мая 2018

Это может быть сделано с небольшой дозой математики.

Если вместо подсчета значений вы можете перечислить их, скажем, тридцать из них для 40, вы получите 

[1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21,
 23, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40]

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

[        1,
 3,  4,  5,
 7,  8,  9,
 11, 12, 13,
 15, 16, 17,
 19, 20, 21,
 23, 24, 25,
 27, 28, 29,
 31, 32, 33,
 35, 36, 37,
 39, 40, (41)]

Другими словами, каждое четвертое число отсутствует, начиная с 2. Вот код, следующий за этим шаблоном: 

const range = (lo, hi) => Array(...Array(hi - lo + 1)).map((_, n) => lo + n)

const countSquareable = (n) => range(1, n).filter(n => n % 4 !== 2).length

console.log(countSquareable(4))
console.log(countSquareable(5))
console.log(countSquareable(40))
console.log(countSquareable(45000))

Так что это соответствует ожиданиям.Но сейчас мы находимся на территории математики, поэтому нам нужно что-то доказать.Мы можем сделать это в трех случаях:

Можно ли представить n в виде разности квадратов?

Случай 1: n нечетный

Пусть a = (n + 1) / 2, пусть b = (n - 1) / 2.

Поскольку n нечетно, n - 1 и n + 1 четные, поэтому a и b оба являются целыми числами. 

a^2 = (n^2 + 2n + 1) / 4
b^2 = (n^2 - 2n + 1) / 4

поэтому 

a^2 - b^2 = 4n / 4 = n

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

Случай 2: n делится на 4

Пусть a = (n / 4 + 1), пустьb = (n / 4 - 1)

Поскольку n делится на 4, (n / 4) is an integer and thus a and b` являются целыми числами.

Now 

a^2 = (n^2/16 + 2n/4 + 1)
b^2 = (n^2/16 - 2n/4 + 1)

и 

a^2 - b^2 = 4n/4 = n

Следовательно, кратное 4 может быть представлено как разность квадратов.

Случай 3: кратное 2, не кратное 4

Мы можемразделите целые числа следующим образом: (4n), (4n + 1), (4n + 2), (4n + 3).

возводя в квадрат каждое из них и выбирая подходящее k, мы получим: 

(4n)^2 = 16n^2 = 4 * 4n^2                             = (4k)
(4n + 1)^2 = (16n^2 + 8n + 1) = 4(4n^2 + 2n) + 1,     = (4k + 1)
(4n + 2)^2 = (16n^2 + 16n + 4) = 4(4n^2 + 4n + 1)     = (4k)
(4n + 3)^2 = (16n^2 + 24n + 9) = 4(4n^2 + 6n + 2) + 1 = (4k + 1)

Таким образом, единственные остатки, возможные при делении квадратана 4 равны 0 и 1.

Вычитая их, мы получаем (1 - 0) = 1, (1 - 1) = 0, (0 - 0) = 0, (0 - 1) = -1 (этот последний аналогичен остатку 3: 4k - 1 = 4 (k -1) + 3.)

Таким образом, мы можем получитьостатки 0, 1 или 3.Но мы не можем получить 2.

Следовательно, кратное 2, не кратное 4, не может быть представлено как разность квадратов.

QED Мы доказали, что наша интуиция верна: любое целое число может быть записано как разностьквадратов, за исключением тех, которые кратны 2, но не 4. 4. 1085 *

Обновление

Мой исходный код был методом грубой силы, отметив, что a^2 - b^2 = (a - b) * (a + b)меньший коэффициент ((a - b)) должен был быть меньше квадратного корня нашего верхнего числа, если произведение было бы меньше n.Затем я попробовал все возможные значения b, сохранив (a^2 - b^2), если оно было меньше n.Это работает и кажется достаточно эффективным для случая 45000.Но он пропускает анализ выше.

В любом случае, вот эта версия: 

const countSquareable = (n) => {
  const found = new Set()
   // a^2 - b^2 = (a - b)(a + b), so (a - b) can be no larger than sqrt(n)
  const topDiff = Math.sqrt(n)
  for (let diff = 1; diff <= topDiff; diff++) {
    const topB = n / 2 // can we get a tighter bound here?
    for (let b = 0; b < topB; b++) {
      let a = b +  diff
      const val = (a * a) - (b * b)
      if (val <= n) {
        found.add(val)
      }
    }
  }
  //console.log([...found].sort((a, b) => a - b))
  return found.size
}

console.log(countSquareable(45000))
...