高精度计算

2025年05月21日 1.4k 字大概 6 分钟

有点意思🫠

题目描述

用高精度计算出 S=1!+2!+3!+⋯+n!（对于 100% 的数据，1≤n≤50）。

其中 ! 表示阶乘，定义为 n!=n×(n−1)×(n−2)×⋯×1。例如，5!=5×4×3×2×1=120。

输入格式

一个正整数 n。

输出格式

一个正整数 S，表示计算结果。

题目来源:洛谷阶乘求和

我的解题思路

首先看到这个题我直接狂喜，这就不是一道”简简单单”的题目吗？(对于还没学习算法的人来说)。所以最开始我的思路就是直接用循环计算阶乘不就好了吗？

#include <iostream>
using namespace std;

void method2()
{
    long long n, ans = 0;
    cin >> n;

    long long factor = 1;

    for (int i = 1; i <= n; ++i) // 循环n次
    {

        factor *= i;
        // for (int j = 1; j <= i; ++j) // 循环i次
        // factor = factor * j;     每次需要重新计算阶乘，时间复杂度为o(n^2)
        ans += factor;
    }

    cout << ans;
}

int main()
{
    method2();
    return 0;
}

问题

后来在debug的时候却发现，当n达到一定程度后，所输出的数甚至会超过long long 的最大数据范围(2^{64} - 1)。这该怎么办？
而且题目还提到了使用高精度，对我这种小白来说，高精度是个啥？
这就是我们要学习的知识。虽然现在许多语言都已经包含了相关的库，但我们还是有必要去了解学习。

高精度

高精度计算（High Precision Computing）是指在数值计算中，使用超出标准数据类型（如 int、long long、float、double 等）所能表示的范围或精度的计算方法。高精度计算主要用于处理非常大的整数、非常小的小数，或者需要极高精度的科学计算场景。

为什么需要高精度计算？

大整数计算：
标准数据类型（如 long long）的范围有限（最大到 (2^{63} - 1)）。如果需要处理更大的整数（如加密算法中的大素数、组合数学中的阶乘等），就需要高精度计算。
例如，计算 1000!（1000的阶乘）的结果远远超出 long long 的范围。
高精度小数计算：
浮点类型（如 float 和 double）虽然可以表示小数，但它们的精度有限（double 精度约为15-17位小数）。对于需要更高精度的科学计算（如天体物理、量子力学等），标准浮点类型无法满足需求。
金融计算：
在金融领域，货币计算需要精确到小数点后多位（如汇率计算、利息计算等），而浮点数的精度误差可能导致不可接受的错误。

高精度计算的实现方式

字符串模拟：
将大整数或高精度小数以字符串的形式存储，然后通过模拟手工计算的方式（如加法、减法、乘法、除法）进行运算。
例如，计算两个大整数的加法时，可以逐位相加并处理进位。
自定义数据结构：
使用数组或其他数据结构存储高精度数值的每一位数字，然后实现相应的运算逻辑。
例如，用一个整数数组存储一个大整数的每一位数字，数组的索引表示位权。
使用高精度库：
许多编程语言提供了高精度计算的库或模块。例如：
C++：Boost.Multiprecision 库。
Python：内置的 decimal 模块和 int 类型（Python的 int 可以自动处理任意大小的整数）。
Java：BigInteger 和 BigDecimal 类。

对于这次的内容来说，我们无疑是要用字符串来实现高精度计算，它的本质就是我们手动来实现数的进位。

代码实现

这次我们直接上代码，再从代码一步步剖析，最后学习代码中的知识点。(参考洛谷题解)

#include <iostream>
#define MAX 100

using namespace std;



void multipal(int x)
{
    int g = 0;
    for (int i = MAX - 1; i >= 0; --i)
    {
        a[i] = a[i] * x + g;
        g = a[i] / 10;
        a[i] %= 10;
    }
}

void get_sum()
{
    int g = 0;
    for (int i = MAX - 1; i >= 0; --i)
    {
        b[i] = b[i] + a[i] + g;
        g = b[i] / 10;
        b[i] %= 10;
    }
}

void print_b()
{
     int w;
    for (int i = 0; i <= MAX - 1; ++i)
    {
        if (b[i] != 0)
        {
            w = i;
            break;
        }
    }

    for (int i = w; i <= MAX - 1; ++i)
        cout << b[i];
}

int a[MAX] = {0}, b[MAX] = {0};

int main()
{
    int n;
    cin >> n;

    a[MAX - 1] = 1;
    b[MAX - 1] = 1;

    for (int i = 2; i <= n; ++i)
    {
        multipal(i);
        get_sum();
    }

    print_b();

    return 0;
}

要想弄明白程序的流程，必然是从主函数入。

1	`int a[MAX] = {0}, b[MAX] = {0};`

这里定义了两个全局变量数组a,b,并初始化为0

1 2	`a[MAX - 1] = 1; b[MAX - 1] = 1;`

这里将数组最后一位数据赋值为1，便于进行接下来的运算

for (int i = 2; i <= n; ++i)
   {
       multipal(i);
       get_sum();
   }

这里进入遍历2-n，同时进入multipal(i)函数中进行。

1	`int g = 0;`

g表示进位，满十进一

for (int i = MAX - 1; i >= 0; --i)//根据数组，我们得知个位是储存在数组的最后一位的
    {
        a[i] = a[i] * x + g;//开始进行累乘
        g = a[i] / 10;//如果g大于10则进一
        a[i] %= 10;//取余
    }

接下来在get_sum()中也很好理解

int g = 0;
    for (int i = MAX - 1; i >= 0; --i)
    {
        b[i] = b[i] + a[i] + g;//最后一位和multipal()函数中相加，以下步骤相同
        g = b[i] / 10;
        b[i] %= 10;
    }

在最后的print_函数中则是输出数组，又因为我们是从最后一位开始计算的，前面的数据有可能并没有填上数据，我们不需要那些数据，直接跳过就好了。
这样整个程序就结束，我们已经大概掌握了如何进行高精度计算。