[C++知识库]C++高精度加法，减法，乘法，除法——四种模板的思路详解自我回顾

学自yxc，整理注释思路供回顾

——————————————————————————————————————————

以下为高精度加法举例：

以96 + 122?= 107为例子

string a= 96? string b= 122

尾插进数组A为 69? ?B为221

Add 函数内部运算

t为进位数，初始化为0，运算实现整体举例以供理解：

从第一位开始相加 ————————————————————————

t = t + 6 + 2 = 8? ,

C.push_back(t%10) 尾插进8

进位为0，t为0

从第二位开始相加————————————————————————

t = t + 9 + 2 = 11?

C.push_back(t%10) 尾插进1

进位数为1，t为1进入第三次循环

从第三位开始相加————————————————————————

由于A数组已遍历完，只加上B数组值，

t = t + 1 = 1 + 1 =2；

C.push_back(t%10) 尾插进2

————————————————————————————————

此时C 数组内存储值为 812

返回数组C，逆序输出 218 = 96 + 122

#include<iostream>
#include<vector>
using namespace std;
vector<int> Add(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    int t=0;//进位数
    for(int i=0;i<A.size() || i<B.size();i++)
    {
        if(i < A.size()) t+= A[i];  //当A，B各自尚未结束遍历时与t进行相加
        if(i < B.size()) t+= B[i];  
        C.push_back(t%10);//  尾插
        t/=10;
    }
    if(t) C.push_back(1);
    return C;
}
int main()
{
    string a,b;//由于数值较大，用字符串进行存储
    vector<int> A;
    vector<int> B;
    cin >> a >> b;
    for(int i=a.size()-1;i >=0;i--) A.push_back(a[i] - '0');//尾插
    for(int i=b.size()-1;i >=0;i--) B.push_back(b[i] - '0');
    auto C = Add(A,B);
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);//逆序输出
    return 0;
}

以上为高精度加法

——————————————————————————————————-————————

以下为高精度减法举例

以 74-28为例子：

string a = 74 ;? string b= 28

同样尾插进数组A为 47? ,B为 82

bool cmp判断思路：使每一次Sub进行的运算时都是第一个数大于第二个数，

初步：A.size() != B.size()? 当两个数组长度不相等时对 A.B长度进行判断，A数组长则返回1，B数组长则返回0.

二步：从A.size（）-1开始遍历，即原数字的首位，当有一位数不相等时候返回，A[I]大时返回1，B[i]大时返回0

三步：遍历完返回True，说明输入的两数相等;

---------------------------------------------------------------------------------------------------------------------------------

Sub函数内部运算:

---------------------------------------------------------------------------------------------------------------------------------

从数组存储的第一位开始相减，同时初始化t=0作为借位使用：

t = A[i] - t =? 4-0 = 4

t -= B[I]? =? 4 - 8 =? -4? ，此时t = -4

C.push_back((t+10)%10);? t+10=6

尾插进6?

if判断是否需要借位，t为-4，t=1表借位

---------------------------------------------------------------------------------------------------------------------------------

?从数组存储的第二位开始相减?

t = A[i] - t =7 - 1 = 6;

t -= B[i] =? 6 - 2 = 4;? t = 4此时

C.push_back((t+10)%10);? t+10= 4

尾插进4

if判断不需要借位，t为0

---------------------------------------------------------------------------------------------------------------------------------

出循环

此时数组C值存储为 64，返回逆序输出即46=74-28；

---------------------------------------------------------------------------------------------------------------------------------

while(C.size() > 1 && C.back()==0) C.pop_back();代码的解释：

当进行运算 20-12运算的时候，

数组C实际存储值为08,但实际输出值为8

所以进行前导0消除后C存储为8

---------------------------------------------------------------------------------------------------------------------------------

对于C.push_back((t+10)%10)代码的思考：

#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int>&A,vector<int>&B)
{
    if(A.size() != B.size()) return A.size()>B.size();
    else
    {
        for(int i=A.size()-1;i>=0;i--)
        {
            if(A[i] != B[i])
            {
                return A[i]>B[i];
            }
        }
    }
    return true;
}
vector<int> Sub(vector<int> &A,vector<int> &B)
{
    vector<int>C;
    for(int i=0,t=0;i<A.size();i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t+10)%10);
        if(t<0) t=1;//借位
        else t=0;
    }
    while(C.size() > 1 && C.back()==0) C.pop_back();

    return C;
}
int main()
{
    string a;string b;
    vector<int>A;vector<int>B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    if(cmp(A,B))
    {
        auto C=Sub(A,B);
        for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    }
    else
    {
        auto C=Sub(B,A);
        printf("-");
        for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    }
    return 0;
}

——————————————————————————————————-————————

以下为高精度乘法举例: PS:实际运算为高精度*低精度:

string a = 154 ,int b = 55

尾插进数组A为451

——————————————————————————————————-————————

Mul函数内部运算:

初始化t为0, ********t为进位数

从数组存储的第一位开始相乘

t += A[i]*b =? 0 + 4*55 = 220

C.push_back(t%10);尾插进0

t /= 10 = 22;

——————————————————————————————————-————————

从数组存储的第二位开始相乘

t += A[i]*b = 22 + 5*55 = 297

C.push_back(t%10) 尾插进7

t /= 10 = 29;

——————————————————————————————————-————————

从数组存储的第三位开始相乘

t += A[i]*b = 29 + 1 * 55 =84;

C.push_back(t%10) 尾插进4

t /= 10 = 8

——————————————————————————————————-————————

此时数组已经遍历完，但由于t不为0，进入循环

C.push_back(t%10) 尾插进8

t /= 10 = 0?

出循环

——————————————————————————————————-————————

此时C数组中存储值为0748

逆序输出即8470

——————————————————————————————————-————————

Mul函数实际运算思路

?前导0的必要性：如1234*0=0，如无前导0实际输出为0000

#include<iostream>
using namespace std;
#include<vector>
vector<int> Mul(vector<int>&A,int b)
{
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        if(i <= A.size())
        {
             t += A[i]*b;
        }
        C.push_back(t%10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    vector<int>A;int b;
    cin >>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    auto C=Mul(A,b);
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    return 0;
}

——————————————————————————————————-————————

以下为高精度除法举例: PS:实际运算为高精度/低精度:

string a = 123? int b = 4

尾插进数组存储为321

——————————————————————————————————-————————

Div函数内部运算：

r为余数,初始化为0

与前面三种运算不同的是，除法需从最高位开始，所以

这里for循环从A.size()-1开始——————————————————————————————————-————————

从数组存储的第一位开始除法运算：

r = r*10+A[i] =? 0 + 1;

C.push_back(r/b) = 1/4?= 0;尾插进0

r %=b = 1%4得余数为1

——————————————————————————————————-————————

从数组存储第二位开始除法运算：

r = r*10+A[i]?= 10 + 2 = 12;

C.push_back(r/b) =? 12/4 = 3;尾插进3

r %=b = 12%4 = 0;余数为0

——————————————————————————————————-————————

从数组存储第三位开始除法运算：

r = r*10+A[i]= 0 + 3 = 3;

C.push_back(r/b) = 3/4 = 0 ,尾插进0

r %=b = 3%4 = 0;余数为3

此时数组中存储为030

——————————————————————————————————-————————

? ? reverse(C.begin(),C.end());

逆序C,逆序后C中存储为030,导0后存储为03

返回C，再次逆序输出C?30? 余数 3

——————————————————————————————————-————————

实际运算思路_代码解释：

r = r*10+A[i];

余数*10加上下一位，即 实际除法运算

?

C.push_back(r/b)?

即实际除法，除几商几

r %=b

求余数 r模等于除数即得到余数，如 1%4 = 1

?reverse(C.begin(),C.end())

该例中无区别，

原因为for循环从A.size()-1开始

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> Div(vector<int>&A,int b,int&r)
{
    vector<int>C;
    r=0;
    for(int i=A.size()-1;i>=0;i--)
    {
        r = r*10+A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;int b;
    cin>>a>>b;
    vector<int>B;
    int r=0;
    for(int i=a.size()-1;i>=0;i--)B.push_back(a[i]-'0');
    auto C=Div(B,b,r);
    for(int i=C.size()-1;i>=0;i--)
    {
    printf("%d",C[i],r);
    }
    cout<<endl<<r<<endl;
    return 0;

}

以上为4种高精度运算模板思路解析

供自我回顾

如有指正在评论区指出