高精度阶乘

常规阶乘

直接上代码

  • 递归：

    1
    2
    3
    4
    long long fac(int n)
    {
        return n==0? 1 : n*fac(n-1);
    }

  • 循环

    1
    2
    3
    4
    5
    sum=1;
    while(i=1;i<=n;i++)
    {
        sum*=i
    }

但是，当阶乘的数值非常大时，递归法和循环法都会出现溢出的问题，无法准确地表示大阶乘的数值。为了解决这个问题，需要使用高精度阶乘算法。

C++ 实现高精度阶乘

为了计算 n! 的值，该程序采用了两个循环嵌套的方式：
外层循环控制阶乘的乘数，内层循环则负责乘法运算。

具体地，先将ans[0]初始化。之后，将外层循环变量i依次从1到n进行循环。在每次外层循环中，内层循环变量j从0到39999进行循环，完成乘法运算，具体计算方式如下：

  1. 计算当前位上的值：将ans[j]乘以i，并加上上一位相乘可能得到的进位x。将乘积对10取模的结果存入ans[j]，作为ans数组当前位的值。

  2. 计算位上的进位：计算向下一位可能得到的进位值x：将ans[j]除以10后得到的值就是当前位上实际得到的进位数。

  3. 初始化ans函数的小细节：如果ans[1]不是1的话计算阶乘最后的结果恒为 0

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int ans[40000]; // 存储阶乘结果的数组（最多输出40000位数）
    int len, n, x = 0; 
    while(cin >> n) 
    {
        len = 39999; 
        memset(ans, 0, sizeof(ans)); // 初始化数组 ans 中所有元素为 0
        ans[0] = 1; // 细节，如果不是1的话计算阶乘最后的结果恒为 0
        x = 0; // 初始化进位为 0
        for(int i = 1; i <= n; i++) // 计算阶乘
        {
            for(int j = 0; j < 4000; j++) 
            {
                ans[j] = i * ans[j] + x; // 计算当前位数的结果(进位前，所以可能大于10)
                x = ans[j] / 10; // 计算进位
                ans[j] %= 10; // 计算当前位数的结果（进位后）
            }
        }

        while(ans[len] == 0) // 从结果的最高位开始找到不为 0 的最低位
        {
            len--; 
        }

        for(;len>=0;len--)
        {
            cout<<ans[len];
        }
        cout<<endl; // 输出结果
    }
    return 0;
}