<html><head></head>
<body><script>
function GCD(a, b) {
if (a == 0) {
return b;
}
return GCD(b % a, a);
}
function difference(array) {
for (var i = Math.min(...array) + 1; i < Math.max(...array); i++) {
array.push(i);
}
array.sort((a, b) => a - b);
}
function smallestCommons(arr) {
difference(arr);
console.log(arr);
a = arr[arr.length - 1];
b = arr[arr.length - 2];
var LCM = a * b / GCD(a, b);
while (true) {
var index = arr.findIndex(element => LCM % element !== 0);
if (index === -1) {
return LCM;
}
LCM *= arr[index];
console.log(LCM);
}
}
smallestCommons([1, 5]) // right
smallestCommons([2, 10]) // right
smallestCommons([1, 13]) // wrong
smallestCommons([23, 18]) // wrong
</script></body>
</html>我使用的算法:
1-计算两个最大数的最小公倍数。
2- 在所有数组上尝试 LCM % number，如果你发现一个不返回 0 的数字，将它分配给 var 索引并乘以它 * LCM 然后继续这样做直到它找不到任何东西并且相反，返回 -1，当发生这种情况时，最终返回 LCM。
代码在前两个数组上有效，但在最后两个数组中不起作用，这让我开始思考，是我的算法错了，我只是在浪费时间尝试调整它，还是它是正确的，它只需要一些调整？
注意有3个不同的函数，第一个函数计算GCD后计算LCM，然后第二个函数压入数组中两个值之间的值然后排序，第三个函数计算LCM(Lowest Common Multiple )
问题是最后一秒数组:
smallestCommons([1, 13]) 返回 4324320 而不是 360360
smallestCommons([23, 18]) 返回 72681840 而不是 6056820
所以我想知道的，请关注这个:
我的整个方法(算法)是错误的，我需要重写整个方法还是需要一些调整才能工作？
请不要给我现成的代码。告诉我我想知道的，谢谢你 (:
最佳答案
你乘以 arr[index] 是错误的。
为了清楚起见，让我们重新标记我们的变量:
N = 数组[索引]
p = GCD(LCM, N)
现在我们可以将 N 和 LCD 重写为:
N = p × q
LCM = p × r
要使最小数字成为当前 LCM 和 N 的最小公倍数，您需要将其计算为:
LCM := p × q × r
但是如果用代码计算的话
LCM *= arr[index];
你实际上计算
LCM := (p × r) × (p × q) = p × p × q × r
即一个 p 因素太多了。要根据需要计算它，您应该改用以下代码:
LCM *= arr[index] / GCD(LCM, arr[index]);
关于javascript - 我的算法是错误的还是正确的，只是需要调整？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51176122/