js实现1万的阶乘

更新日期: 2019-08-23阅读量: 1351标签: 算法

前言

最近面试的时候遇到一道面试题,就是实现10000!,当时的第一反应是直接用递归实现:

function factorial_recursion(n){
    if(n <= 1) return 1;

    return n * factorial_recursion(n-1)
}

但是这样就会存在问题,js中最大的安全整数为2^53- 1,10000!结果溢出该范围,代码运行结果为Infinity,无法计算出正确的结果。
那么如何才能计算大数据的阶乘呢?


BigInt

可以使用js最新的基本数据类型BigInt,BigInt数据类型支持范围更大的整数值,可以解决整数溢出问题。
BigInt数据通过BigInt构造函数创建,修改代码如下:

function factorial_recursion(n){

    if(n <= 1) return 1;

    return BigInt(n) * BigInt(factorial_recursion(n-1))
}

通过factorial_recursion(10000)就可以得出结果。
但当计算更高数值的阶乘时,比如求20000的阶乘,出现栈溢出的情况。
那么如何才能解决栈溢出问题?


平方差实现

算法思路
可以从减少乘法运算的次数角度出发,阶乘运算可转换为若干个平方差的积,使得阶乘只需要n/2次乘法,并且得出规律平方差之间的差是连续的奇数。除了平方差乘数,其他乘数根据n为奇数或偶数也有不同规律。
算法分析

当计算9的阶乘时:
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 

取中间值为基值: (5 - 4) * (5 - 3) * (5 - 2) * (5 - 1) * 5 * (5 + 1) * (5 + 2) * (5 + 3) * (5 +4)

调换位置:(5 - 1) * (5 + 1) * (5 - 2) * (5 + 2) * (5 - 3) * (5 + 3) * (5 - 4) * (5 + 4) * 5

合并为平方差:(5^2 - 1) * (5^2 - 2^2) * (5^2 - 3^2) * (5^2 - 4^2) * 5

计算平方差结果: 24 * 21 * 16 * 9  

得出规律:24、21、16、9之间的差分别为基数3、5、7,奇数基础乘数为 n / 2

当计算10的阶乘时:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

取中间值位基值: (5 - 4) * (5 - 3) * (5 - 2) * (5 - 1) * 5 * (5 + 1) * (5 + 2) * (5 + 3) * (5 +4) * (5 + 5)

调换位置:(5 - 1) * (5 + 1) * (5 - 2) * (5 + 2) * (5 - 3) * (5 + 3) * (5 - 4) * (5 + 4) * 5 * (5 + 5)

合并为平方差:(5^2 - 1) * (5^2 - 2^2) * (5^2 - 3^2) * (5^2 - 4^2) * 5 * (5 + 5)

平方差结果: 24 * 21 * 16 * 9  

得出规律:24、21、16、9之间的差分别为基数3、5、7,偶数基础乘数为 n / 2 * n


代码实现如下:

function factorial_square(n){
    if(n <= 1) return 1;
    const middle = Math.ceil(n / 2);    //取中间值
    let tmp = middle * middle,
        result = n & 1 == 1 ? middle : middle * n;  //奇偶数的基础乘数规律不同
    for(let i = 1 ; i <= n - 2 ; i += 2){   //连续减奇数得出各项乘数
        tmp -= i;
        result = BigInt(result) * BigInt(tmp);
    }
    return result;
}

BigInt兼容性并不友好,Chrome浏览器在67+版本中才支持该数据类型。
在不支持BigInt的浏览器中怎么计算大数据阶乘呢?


数组存储实现

算法思路
可以使用数组来存储大数据结果的每位数,如result[0]存储个位数,result[1]存储十位数,以此类推。计算每位数时需要加上上一个位数得出的进位,最后再将数组反转并拼接,就可以得出大数据结果。
算法分析
以5! = 1 5为例:


代码实现

function factorial_array(n){
let result = [1],   //存储结果
    digit = 1,      //位数,从第1位开始
    count ,         //每次计算的结果
    num ,           //阶乘的计算到的第几个
    i ,             //result中每一项
    carry;          //每次得数的进位

for(num = 2 ; num <= n ; num++){
    for(i = 1 , carry = 0 ; i <= digit ; i++){
        count = result[i - 1] * num + carry;        //每一项计算结果
        result[i - 1] = count % 10;                 //将一个数的每一位数利用数组进行储存
        carry = (count - result[i - 1]) / 10        //记录进位
    }

    while (carry) { //如果还有进位,继续存储
        result[digit] = carry % 10;
        carry = (carry - result[digit]) / 10;
        digit++;
    }
}
return result.reverse().join("");
}


总结

1.递归实现
优点:实现代码简单,速度快
缺点:较大数据容易出现栈溢出,兼容性不够友好
2.平方差实现
优点:乘数计算少,速度快
缺点:兼容性不够友好
3.数组存储实现
优点:数组清晰地存放大数据的每个位数,每次计算时能简单地从低位到高位求值
缺点:需要用数组存储大数据的每位数,需要占用较大内存,速度较慢


站长推荐

1.云服务推荐: 国内主流云服务商/虚拟空间,各类云产品的最新活动,优惠券领取。领取地址:阿里云腾讯云硅云

链接: https://www.fly63.com/article/detial/5491

原生js实现冒泡排序算法,javascript冒泡排序

javascript冒泡排序的实现,冒泡排序是一个非常常见的排序算法,对于一个数组,每趟排序时依次比较两个相邻的数,如果他们的顺序错误就交换两数位置。

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!