C++ 高精度算法（并附实例）

2021年8月12日 | 分类: 【编程】

参考：https://blog.csdn.net/actioncms/article/details/105148549

一、本质

高精度算法的本质在于将复杂变为简单

实现的原理是小学学过的列式计算

将每一位进行逐步运算

二、代码

高精加

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
49
50
51
/*======================================
高精度加法
不考虑负数（高精减来处理负数）
字符接收再转为整数数组
注意颠倒，注意消除前置0
核心在于 a 数组 + b数组 = c数组
核心代码为:
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;
=======================================*/
  
#include <iostream>
  
using namespace std;
  
string s1,s2;
int a[1000];
int b[1000];
int c[1001];
  
int main()
{
    cin >>s1 >>s2;
    int la=s1.length();
    int lb=s2.length();
  
    for (int i=0;i<la;i++)
    {
        a[la-i] = s1[i] - '0';    //转化接收
    }
    for (int i=0;i<lb;i++)
    {
        b[lb-i] = s2[i] - '0';
    }
  
    int lc = max(la,lb)+1;       //c数组的长度
    for (int i=1;i<=lc;i++)
    {
        c[i] += a[i] + b[i];     //核心代码
        c[i+1] = c[i]/10;
        c[i] = c[i]%10;
    }
  
    if (c[lc]==0 && lc>0) lc--;  //消除前置0
    for (int i=lc;i>0;i--)
    {
        cout <<c[i];
    }
    return 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*=========================================
高精度减法
输入的也是两个正数
flag是对正负号的跟踪判断
comp函数还是需要深入理解下（判断是否换位）
==========================================*/
  
#include <iostream>
#include <string>
  
using namespace std;
  
string s1,s2;
string s3;
bool flag=0;
  
int a[10100],b[10100],c[10100];
  
bool comp(string a,string b)
{
    int la=a.length();
    int lb=b.length();
    if (la!=lb) return la>lb;
    else
    {
        for (int i=0;i<la;i++)
        {
            if (a[i]!=b[i])
            {
                return a[i]>b[i];
                break;
            }
        }
    }
}
  
int main()
{
    cin >>s1 >>s2;
  
    if (!comp(s1,s2))
    {
        s3=s1;
        s1=s2;
        s2=s3;
        flag=1;                 //若换位则改变 flag
    }
  
  
    int la=s1.length();
    int lb=s2.length();
    for (int i=0;i<la;i++)
    {
        a[la-i]=s1[i]-'0';
    }
    for (int i=0;i<lb;i++)
    {
        b[lb-i]=s2[i]-'0';
    }
    int lc=max(la,lb);          //与加法不同 c 数组的长度最多是 a，b中较长那个
    for (int i=1;i<=lc;i++)
    {
        if (a[i]<b[i])          //借位判断
        {
            a[i+1]--;           //不够则向上位借1
            a[i]+=10;           //本位+10
        }
        c[i]=a[i]-b[i];
    }
  
    while (c[lc]==0&&lc>1) lc--;  //消除前置0，方法与高精加略有不同
    if(lc==1&&c[0]==0) flag=0;    //相减为0的情况下不输出 - 号
    if(flag) cout <<"-";
  
    for (int i=lc;i>0;i--)
    {
        cout <<c[i];
    }
  
    return 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
38
39
40
41
42
43
44
45
46
47
48
/*=========================================
高精乘
核心算法：（列式计算中找出的规律）
c[i+j-1] += a[i] * b[j];
c[i+j] += c[i+j-1]/10;
c[i+j-1] %= 10 ;
==========================================*/
  
#include <iostream>
#include <string>
  
using namespace std;
  
string s1,s2;
int a[2008],b[2008],c[2008];
  
int main()
{
    int la,lb,lc;
    cin >>s1 >>s2;
    la=s1.length();
    lb=s2.length();
  
    for (int i=0;i<la;i++)
    {
        a[la-i]=s1[i]-'0';
    }
    for (int i=0;i<lb;i++)
    {
        b[lb-i]=s2[i]-'0';
    }
    lc=la+lb;                          //c 数组的位数不会超过其和
    for (int i=1;i<=la;i++)
    {
        for (int j=1;j<=lb;j++)
        {
            c[i+j-1] += a[i]*b[j];     //核心算法
            c[i+j] += c[i+j-1]/10;     //进位
            c[i+j-1] %= 10;            //留位
        }
    }
    if (c[lc]==0&&lc>0) lc--;          //消除前置零
    for (int i=lc;i>0;i--)
    {
        cout <<c[i];
    }
    return 0;
}

三、总结&感想

学习的道路上艰辛却又看不见终点

好在大家走的路都是相似的

前人铺垫好的

我们感谢、使用、完善

例如，在减法中存在一个借位判断

在之后可能就会遇到别的相似判断

附上一道题，洛谷 P1009 阶层之和（写一起主要是懒得再写一篇了 ps：洛谷是一个网站啦）

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
49
50
51
52
53
54
55
56
57
58
59
/*===============================
阶层之和很简单，一个循环就能搞定
但是只限于数目较小的时候
通过这一道题目来初步学习高精度算法
高精度就是说参与运算的数据和运算结果的范围
超出标准数据类型能表示的数据大小范围的运算
================================*/
  
/*================================
核心还是高精算法
关键还是把握整体思路
中间有一个判断
和借位判断类似
像是一个进位判断
================================*/
  
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[2000];
int b[2000];
  
int main()
{
    a[1]=1;
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<100;j++)         //50个二位数一下累乘位数不会超过100
        {
            a[j] *= i;                  //每一位先乘
        }
        for (int j=1;j<100;j++)
        {
            if (a[j]>9)                 //进位判断
            {
                a[j+1]+=(a[j]/10);
                a[j] %= 10;
            }
        }
        for (int k=1;k<100;k++)
        {
            b[k] += a[k];               //累加进入 b 数组
            if (b[k]>9)
            {
                b[k+1] += (b[k]/10);
                b[k] %= 10;
            }
        }
    }
    int ws=100;                         //消除前置0（定义出一个位数）
    while(b[ws]==0) ws--;
  
    for (int i=ws;i>0;i--)
    {
        cout <<b[i];
    }
}