javascript - 使循环和代码更有效地使用循环处理大量数字

Question

这是 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

如何使代码更有效地解决问题？型是here 。谢谢!!

Answer 1

这可以通过少量的数学计算来完成。

如果您可以列出它们，而不是计算值，例如 30 个值等于 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一个and b` 是整数。

现在

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 。

因此，不是 4 的倍数的 2 的倍数不能表示为平方差。

Q.E.D。我们已经证明了我们的直觉是正确的:任何整数都可以写成平方差，除了那些是 2 的倍数但不是 4 的倍数的整数。

<小时/>

更新

我的原始代码是一种暴力方法，注意到 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))