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
#include
using namespace std;
vector Add(vector &A,vector &B)
{
    vector C;
    int t=0;//进位数
    for(int i=0;i A;
    vector 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
#include
using namespace std;
bool cmp(vector&A,vector&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 Sub(vector &A,vector &B)
{
    vectorC;
    for(int i=0,t=0;i 1 && C.back()==0) C.pop_back();

    return C;
}
int main()
{
    string a;string b;
    vectorA;vectorB;
    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
using namespace std;
#include
vector Mul(vector&A,int b)
{
    vectorC;
    int t=0;
    for(int i=0;i 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    vectorA;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
#include
#include
using namespace std;
vector Div(vector&A,int b,int&r)
{
    vectorC;
    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;
    vectorB;
    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< 
以上为4种高精度运算模板思路解析
 
供自我回顾
 
如有指正在评论区指出