[基础算法](3)高精度

引言

高精度算法就是利用程序模拟我们小学学的 竖式算术法 利用 string 分别存储 两个大数 由于考虑进位问题 在 加法 、乘法 、减法的模拟算法都需要从前往后计算,所以需要转换为逆序vector，则 int [0] = a[a.size()]

高精度加法

模板题:791. 高精度加法 - AcWing题库

代码:

#include<iostream>
#include<vector>
using namespace std;
string a,b;
vector<int >A,B;

//高精度加法模板:
vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int i,t;//t为进位
    for (i = 0, t = 0; i < A.size(); i++) {
        t = A[i] + t;
        if (i < B.size()) t += B[i];//若B有 则加
        C.push_back(t % 10);
        t /= 10;
    }
    while (i < B.size()) C.push_back(B[i] + t % 10), t = (B[i] + t) / 10,i++;//处理B剩余的数
    if(t) C.push_back(t);
    return C;
}

int main(){
    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');
    vector<int >C = add(A,B);

    for(int i=C.size()-1;i>=0;i--) cout<<C[i];

    return 0;

}

高精度减法

模板题:792. 高精度减法 - AcWing题库

代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//比较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;
}

//高精度减法模板
//由于保证了 A > B 恒成立,则有最高位相减时不会向前借位
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];//判断B在这一位是否有数字，若有，则减去
        C.push_back((t + 10) % 10);//存储这一位的值,加上向前借位的值取个位
        if (t < 0) t = 1;//若t原本小于0，则代表需要向前借位，则将其初始为1
        else t = 0;//否则不需要借位，则为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;

    //逆序存储，为了更好的存储借位情况
    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');

    vector<int> C;

    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];

    return 0;

}

高精度乘法

模板题:793. 高精度乘法 - AcWing题库

代码:

#include<iostream>
#include<vector>
using namespace std;
string a;
int b;
vector<int >A, B;

//高精度乘整数模板:
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int i, t;
    for (i = 0, t = 0; i < A.size()||t; i++) {
        if (i < A.size()) t = A[i] * b + t;//计算该位的值
        C.push_back(t % 10);//存储该位
        t /= 10;//处理进位
    }
    while (t) C.push_back(t % 10), t /= 10;//处理进位
    while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
    return C;
}

int main() {
    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--) cout << C[i];
    return 0;
}

这里给出 [ 高精度 * 高精度 ] 的代码:此代码应用到北大OJ1001题目中，笔记入口:北大OJ求幂算法 - Null'Blog (nullcode.fun)

void chen(char a[], char b[])
{
    int c[410] = { 0 };
    int i, j, sum, k, k1;
    k = 409;
    k1 = 409;
    for (i = strlen(a) - 1; i >= 0; i--)
    {
        for (j = strlen(b) - 1; j >= 0; j--, k--)
        {
            sum = (a[i] - '0') * (b[j] - '0') + c[k];
            c[k - 1] = c[k - 1] + sum / 10;
            c[k] = sum % 10;
        }
        k = --k1;
    }
    for (i = 0; i < 410; i++)
    {
        if (c[i] != 0)
        {
            break;
        }
    }
    for (j = i, i = 0; j < 410; i++, j++)
    {
        b[i] = c[j] + '0';
    }
    b[i] = 0;
}

高精度除法

模板题:794. 高精度除法 - AcWing题库

代码：

#include<iostream>
#include<vector>
using namespace std;
string a;
vector<int> A;
int b;

vector<int> dev(vector<int>& A, int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i++) {
        t = t * 10 + A[i];//上一位的余数加上这一位的数形成新的被除数
        C.push_back(t / b);//除去除数
        t %= b;//更新余数
    }
    reverse(C.begin(), C.end());//将答案反转过来 去除前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main() {
    cin >> a >> b;
    for (int i = a.size(); i >= 0; i--) A.push_back(a[i] - '0');

    auto C = dev(A, b);

    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];

    return 0;
}

本文链接：