代码之家 › 专栏 › 技术社区 › noirsociety

关于勒让德公式和递归的问题?

ecmascript-6 recursion algorithm javascript

noirsociety · 技术社区 · 3 年前

我现在正在学习勒让德公式。到目前为止,我能够用以下方法解决算法:

const legendre = (p,n,res=0) => Array.from({length:n},(_,i) => res+=Math.floor(n/p**++i)) && res;

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

然而,我就是不能反复地克服这个困难。这就是我目前的情况:

const legendre = (p,n,i=1,res=0) => p > n ? res : res + legendre(p**i,n,i+1,Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 99 
console.log(legendre(3,60)); // 26
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 300

正如你所见,大多数结果都是错误的。我走对了吗?有人能帮我指出正确的方向,或者告诉我我做错了什么吗?任何反馈都将不胜感激。万分感谢:)

1 回复 | 直到 3 年前

Samathingamajig 3 年前

我首先将您的第一个代码转换为普通函数:

const legendre = (p, n) => {
  let res = 0;
  for (let i = 1; i <= n; i++) {
    res += Math.floor(n/p**i);
  }
  return res;
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

并将其转换为递归函数:

const legendre = (p, n, i=1, res=0) => {
  // base case -> done
  if (i > n) return res + Math.floor(n/p**i);
  return legendre(p, n, i+1, res + Math.floor(n/p**i));
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

可以做成这样的一行:

const legendre = (p,n,i=1,res=0) => i > n ? res + Math.floor(n/p**i) : legendre(p,n,i+1,res +Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

我没有研究过这个算法,这些答案只是基于您的第一个代码片段和测试用例。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前