c/c++高精度算法

前言

大一上学期刚刚开始学习算法，第一课就是模拟，模拟的第一题就是高精度加法，随后又有乘法，减法，除法。刚开始手搓起来相当难受，没有总结，每一道新题的高精度算法都像是在第一次写，费时间不说，还常常出错，现在刚好找个时间在此总结一下。

高精度算法：由于 c 语言或者 c++中，给定的数据范围有限，在一些对于较大数据的计算时候，无法直接由数据进行加减乘除运算去得到最后正确的答案，所有就需要借助字符串模拟大数据的算术式，模拟计算过程得到答案，这就是所谓的高精度加减乘除算法。（语言不好理解，往下看！）

加法前言

对于加法，在一些 c++可以处理的数据内，进行加法运算相当简单（下面代码用 c++演示，与 c 语言语法基本一致，只学过 c 语言也能看懂）

1
2
3
int a = 100, b = 100;
int c = a + b;
printf("%d", c);

这样子显然没问题，因为数据很小，语言处理得过来，但是！我们知道 int 类型最大值为 2147483647，而 long long 类型最大值为 9223372036854775807‌，当变量的值超过了最大值，就会出现错误！

开始思考：回想起小学就会滴算术式，9223372036854775807‌ + 9223372036854775807‌ = ？

  9223372036854775807‌
+ 9223372036854775807‌
----------------------
 18446744073709551614

列出上面这样的算术式，从末位开始相加，如果和大于 10 的就进位到前一位去求和，以此类推。于是我们想到是否可以用语言去模拟这个计算过程呢？整个过程就是多次计算最多 3 个小数字的和，通过处理多个小数字和，然后求出大数据的和，这就是高精度加法。那么接下来，开始快乐模拟！

高精度加法

整体过程：输入两个要求和的字符串，最后输出一个字符串为结果

重要步骤：1.将输入的两个字符串倒序转换为整数型数组。

         2.两个数组的各位数组分别求和，并存入一个新数组.

         3.处理新数组，模拟实现进位，然后输出结果。

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
38
39
40
41
42
43
#include <iostream>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.length();
    int len2 = s2.length();
    //数组用来转换存储字符串的，大小根据需要定义
    int a[10000], b[10000];
    //用来存储答案
    int c[20000];
    for (int i = 0;i < len1; i++)
    {
        //倒序存入，并将字符通过相差‘0’转换为整数（ascll码表）
        //注意这里的存入数组a[0]和b[0]都是没有存入的，最小序数是1
        a[len1 - i] = s1[i] - '0';
    }
    for (int i = 0;i < len2; i++)
    {
        b[len2-i] = s2[i] - '0';
    }
    //c数组的长度，求和结果的位数一定不会超过较大值位数加1（自己写几个想想）
    int len3 = max(len1, len2) + 1;
    //注意从序数1开始！
    for (int i = 1;i <= len3; i++)
    {
        //核心代码，求和存入数组c中，注意是+=，因为数组c中会有前一位的进位要一起求和。
        c[i] += a[i] + b[i];
        //大于10就进位给下一位
        c[i + 1] = c[i] / 10;
        //保留个位数
        c[i] = c[i] % 10;
    }
    //因为刚才的位数len3是考虑的最大情况，这里需要清除可能没用到前置0（停下来思考一下）
    if (c[len3] == 0 && len3 > 0) len3--;
    for (int i = len3; i > 0; i--)
    {
        //倒序输出答案，cout输出，c语言的printf
        cout <<c[i];
    }
    return 0;
}

乘法高精度

在计算乘法高精度时，我分成两类学习，第一：大数字乘小数字（大数字指的是用字符串存的数字，小数字是可以之间用数据类型表示的数字）第二：大数字乘大数字

第一类

此类的重要步骤与加法的相似

重要步骤： 1.将输入的大数字的字符串倒序转换为整数型数组。

          2.让数组的各位数字分别与小数字求积。

          3.处理数组，模拟实现进位，然后输出结果。

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
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
int main()
{
    string s;
    int low;
    //输入两个乘数，一个大一个小
    cin >> s >> low;
    //定义一个存放大数据的数组，最终也作为答案输出
    int a[10000];
    int len = s.length();
    for (int i = 0;i < len; i++)
    {
        //倒序存入，并将字符通过相差‘0’转换为整数（ascll码表）
        //注意这里的存入数组a[0]和b[0]都是没有存入的，最小序数是1
        a[len - i] = s[i] - '0';
    }
    //下面开始乘积
    for (int i = 1; i <= len; i++)
    {
        //数组每一位都乘于小数字
        a[i] *= low;
        //上一位进位到下一位（注意+=，用 = 会数据覆盖了哦）
        a[i] += a[i - 1] / 10;
        //上一位保留个位数
        a[i - 1] %= 10;
    }
    //最后一位的进位还没有完成！
    //如果最后一位ie是大于9的，就得进位
    while (a[len] > 9)
    {
        //进位！
        a[len + 1] = a[len] / 10;
        a[len] %= 10;
        //更新最后一位的位数，因为循环判断的就是a[len]
        len++;
    }
    //最后输出，注意是倒序输出！
    for (int i = len; i > 0; i --)
    {
        cout << a[i];
    }
    return 0;
}

第二类

大数字乘大数字（此类是高精度乘积的通法，第一类也可以用这个解决，只是我更喜欢区分开，因为个人认为法一更好写）

我们不妨从较小数字相乘来找规律，243 * 512 = 124416

首先 243 = （2*100）+（4*10）+3

     512 = （5*100）+（1*10）+2

由乘法分配律得知，两数相乘，就是将上下 3 者分别相乘再相加

于是我们进一步思考，两数的个位 2,3 相乘其实就是结果积的个位，而 512 的个位 2 与 243 的十位 4 相乘其实是 240，它对结果的影响一定从十位开始（不可能影响个位），再然后 512 的个位 2 与 243 的百位 2 相乘 其实是 2200,它对结果的影响一定从百位开始（不可能影响个位和十位）

于是！我们找到规律！我们可以认为两个乘数的个位相乘的积，加为结果的个位上；一个个位一个十位的积，加为结果的十位，一个个位一个百位或者两个十位的积，加为结果的百位………以此类推！

最终再进行模拟进位。代码如下：

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
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.length();
    int len2 = s2.length();
    //数组用来转换存储字符串的，大小根据需要定义
    int a[10000], b[10000];
    //用来存储答案
    int c[20000];
    for (int i = 0;i < len1; i++)
    {
        //倒序存入，并将字符通过相差‘0’转换为整数（ascll码表）
        //注意这里的存入数组a[0]和b[0]都是没有存入的，最小序数是1
        a[len1 - i] = s1[i] - '0';
    }
    for (int i = 0;i < len2; i++)
    {
        b[len2-i] = s2[i] - '0';
    }
    //接下来开始核心代码，乘积规律模拟
    //首先由规律知道，结果位数不会超过两乘数位数和加2,所以待定结果位数如下
    int len = len1 + len2;
    //外循环遍历数组a，注意i对应a
    for (int i = 1; i <= len1; i++)
    {
        //内循环遍历数组b，注意j对应b
        for (int j = 1; j <= len2; j++)
        {
            //下面就是对规律的代码模拟，不理解的再看一次上面的找规律文字过程
            c[i + j - 1] += a[i] * b[j];
            //进位模拟
            c[i + j] += c[i + j - 1] / 10;
            //保留每位小于10
            c[i + j - 1] %= 10;
        }
    }
    //因为刚才的位数len是考虑的最大情况，这里需要清除可能没用到前置0（与上面高精度加法一样）
    if (c[len] == 0 && len > 0) len--;
    //最后循环倒序输出答案！
    for (int i = len; i > 0; i--)
    {
        cout << c[i];
    }
    return 0;
}

至此高精度乘法解决