使循环和代码更有效地处理带有循环的大数字
Make loop and code more efficient to handle large numbers with loops
这是 Codewars 上的作业，换句话说就像家庭作业。 :)
我必须编写一个函数，其中 returns 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。
谢谢！！
这需要一点数学知识。
如果您可以列出它们而不是计算值，比如 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可以表示为平方差吗？
情况一：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 thusaandb` 是整数。
现在
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：不是 4 的倍数的 2 的倍数
我们可以这样划分整数：(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 的所有可能值，如果小于 n，则保存 (a^2 - b^2)。这有效，并且对于 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))
这是 Codewars 上的作业，换句话说就像家庭作业。 :)
我必须编写一个函数，其中 returns 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。 谢谢！！
这需要一点数学知识。
如果您可以列出它们而不是计算值，比如 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可以表示为平方差吗？
情况一：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 thusaandb` 是整数。
现在
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：不是 4 的倍数的 2 的倍数
我们可以这样划分整数：(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 的所有可能值，如果小于 n，则保存 (a^2 - b^2)。这有效，并且对于 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))