高精度（加、减、乘、除）

高精度加法

算法思想

1.将高精度数用字符串表示string a，b，再用vector用数组表示vector A,B，再调用push_back方法逆序存储，存储由低位向高位存储，这样进位时方便存储，即原始数为”123456”,则存储在数组中的值为[6,5,4,3,2,1].
2.设置进位t 本位的值等于(t + A[i] + B[i])%10
然后传给下一位的进位为 t = (t + A[i] + B[i])/10
3.如果处理完最后进位t存在的话，则将数组最后以为置1\

完整代码

#include<iostream>
#include<vector>
using namespace std;

//C = A + B  大整数加法
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];
        if(i < B.size()) t += B[i];             //t = t + a[i] + 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,B;
    cin >> a >> b;  //a = "123456"
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');//A = [6,5,4,3,2,1,]
    for(int i = b.size() - 1;i >= 0;i --) B.push_back(b[i] - '0');
    auto C = add(A,B);                  //自动返回对应的类型也就是vector<int>
    for(int i = C.size() - 1;i >= 0;i--) printf("%d",C[i]);
    return 0;
}

代码模板

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];
        if(i < B.size()) t += B[i];             //t = t + a[i] + b[i]
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(1);
    return C;
}

高精度减法

算法思想

需先判断A与B的大小，因为如果A比B小的话，相减为负数，则应转换为-(B-A),设置cmp()函数，进行两个数之间的大小比较\
设置来自低位的借位t，先进行t = A[i] - t(每次都要减去来自上一位的借位),判断此时B[i]是否有数，若有的话则，t = t - b[i]；此时本位的值为(t + 10) % 10; 如果此时t < 0,则说明要向上以为借1，则此时令t = 1；否则的话t = 0，重复上述操作，直到遍历完数组A中所有的数\
得到的结果可能存在高位有0的前导0现象。要做的处理就是将高位为0的数全部弹出，最多只保留1位位0.\

完整代码

#include<iostream>
#include<vector>
using namespace std;

//C = A - B  大整数减法
//判断是否有 A>-=B
bool cmp(vector<int> &A,vector<int> &B){
    if(A.size() != B.size()) return A.size() > B.size();
    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];             //t = t + a[i] + 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();  //去掉前导0
    return C;
}

int main(){
    string a,b;
    vector<int> A,B;
    cin >> a >> b;  //a = "123456"
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');//A = [6,5,4,3,2,1,]
    for(int i = b.size() - 1;i >= 0;i --) B.push_back(b[i] - '0');
    if(cmp(A,B)){
        auto C = sub(A,B);//自动返回对应的类型也就是vector<int>
        for(int i = C.size() - 1;i >= 0;i--) printf("%d",C[i]);
    }else{
        auto C = sub(B,A);//自动返回对应的类型也就是vector<int>
        printf("-");
        for(int i = C.size() - 1;i >= 0;i--) printf("%d",C[i]);
    }
    return 0;
}

模板代码

//C = A - B  大整数减法
//判断是否有 A>-=B
bool cmp(vector<int> &A,vector<int> &B){
    if(A.size() != B.size()) return A.size() > B.size();
    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];             //t = t + a[i] + 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();  //去掉前导0
    return C;
}

高精度乘法

算法思想

算法的主要思想就是将A[i]中每位数都与b相乘，判断其余数（就是C[i]）,而商就是进位，多次循环即可求出结果\
设置进位t，如果此时A[i]中还有数的话则t = t + A[i] * b,C[i] 就等于 t % 10，产生的下一位进t = t / 10；重复上诉操作，循环的条件是A[i]没有遍历完，或者t还存在不为0\

完整代码

#include<iostream>
#include<vector>
using namespace std;

//C = A * b  大整数乘法
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;
    }
    return C;
}

int main(){
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    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;
}

模板代码

//C = A * b  大整数乘法
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;
    }
    return C;
}

高精度除法

算法思想

除法与前面三种算法不同，除法是从最高位开始进行计算的，所以在循环的条件i是从A.size() - 1开始。\
r为余数，进入循环时r = r*10 +A[i],则此时的商为r / b也就是C,则此时的余数为r = r % b.循环上述操作直到遍历完A[]中所有的数。\
因为此时C[]中的数是由高位到地位的，所以要调用reverse()方法，将其倒置，以保证其输出方式与前面三种算法相同\
同时该算法也存在前导0的问题，与前面算法的处理相同。\

完整代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// A / b 商是c，余数是r
vector<int> div(vector<int> &A,int b,int &r){           //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> A;
    for(int i = a.size()-1;i >=0;i --) A.push_back(a[i] - '0');
    int r;
    auto C = div(A, b, r);
    for(int i = C.size() - 1;i >= 0;i --) printf("%d",C[i]);
    cout << endl;
    cout << r << endl;
    return 0;
}

模板代码

// A / b 商是c，余数是r
vector<int> div(vector<int> &A,int b,int &r){           //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;
}

算法基础 > 第一章

高精度

https://lzyjx.github.io.git/2023/04/20/Highprecision/

作者

六只羊

发布于

2023年4月20日

许可协议

前缀和与差分上一篇

第二章JSP语法下一篇