全面的前端编程教程 - 秘密武器开发者中心

热搜:m1 代理 前端 301

阶乘算法

2021-04-05 01:36:06

阶乘

一个正整数的阶乘factorial)是所有小于及等于该数的​正整数​的​​,并且0的阶乘为1。自然数n的阶乘写作​n!

如果使用字母​n​代表一个整数,则阶乘是所有小于或等于​n​的整数的乘积。

阶乘通常简写成 ​n!​例如: 5! = 1 * 2 * 3 * 4 * 5 = 120。
 

function factorialize(num) {
    var nBefore = 0;
    var nAfter = 1;
    for(var n = 1; n <= num; n++){
      nBefore = n;
      nAfter = nBefore * nAfter;
    }
    return nAfter;
}

/**
 * 递归解法
 */
/*
function factorialize(num) {
  return num === 0 ? 1 : num * factorialize(num - 1);
}
*/

 

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5));  // 输出: 120

这个factorial函数检查输入的数是否是0或者1,若是的话,返回1,因为0!和1!都是1。否则的话,它会使用自身(递归调用),来计算n * factorial(n - 1),这就是阶乘的定义。

这段代码里的console.log(factorial(5));就是利用了定义的该函数来计算5!的值,并输出结果。

注意: 在使用递归方法时需要考虑到调用深度和性能问题,过大的数值可能导致调用达到最大限制或耗尽系统资源。对于大数值输入,你可能需要使用循环或其他更优的算法。

更优一点的算法

function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorial(5));  // 输出: 120

这个函数的工作方式是初始化result为1,然后使用一个for循环,从2循环到n(包括n),每次增加结果与当前数的乘积。这种方式比递归的方式更高效,因为它不需要创建新的函数调用栈,而且工作量是线性的,即O(n)。

另外,如果输入的数字很大,JavaScript的数字类型可能无法精确表示阶乘的结果。这种情况下可以考虑使用大数库,比如BigInt来实现!

function factorial(n) {
  let result = BigInt(1);
  for (let i = BigInt(2); i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorial(BigInt(50)); // 输出: 30414093201713378043612608166064768844377641568960512000000000000n
 

 

js