常用算法讲解--高精度篇

科技起源

2025-07-30 11:32:46

发布于：河北

7阅读

0回复

0点赞

高精度没什么好说的，为了解决+-*/时

本质上就是模拟竖式

这里只提供代码模版（根据数据范围自行修改）

- 高精度加法

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
const int N = 1000000 + 10;
int a[N];
int b[N];
int c[N];

int main(){

    cin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();
    for (int i = 1;i <= len1;i++){
        a[i] = s1[len1 - i] - '0';
    }
    for (int i = 1;i <= len2;i++){
        b[i] = s2[len2 - i] - '0';
    }
    for (int i = 1;i <= 1000000;i++){
        c[i] += a[i] + b[i];
        c[i + 1]+=c[i] / 10;
        c[i] %= 10;
    }

    int lc = 1000002;
    while(c[lc] == 0 && lc > 1){
        lc--;
    }
    for (int i = lc;i >= 1;i--){
        cout << c[i];
    }

    return 0;
}

- 高精度减法

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
const int N = 1000000 + 10;
int a[N];
int b[N];
int c[N];

int main(){

    cin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();
    bool flag = false;
    if (len1 < len2){
        swap(len1, len2);
        swap(s1, s2);
        flag = true;
    } else if (s1 < s2 && len1 == len2){
        swap(s1, s2);
        flag = true;
    } else {
        flag = false;
    }
    for (int i = 1;i <= len1;i++){
        a[i] = s1[len1 - i] - '0';
    }
    for (int i = 1;i <= len2;i++){
        b[i] = s2[len2 - i] - '0';
    }
    for (int i = 1;i <= 1000000;i++){
        c[i] += a[i] - b[i];
        if (c[i] < 0){
            c[i] += 10;
            c[i + 1]--;
        }
    }

    int lc = 1000002;
    while(c[lc] == 0 && lc > 1){
        lc--;
    }
    if (flag == 1){
        cout << "-";
    }
    for (int i = lc;i >= 1;i--){
        cout << c[i];
    }

    return 0;
}

- 高精度乘法

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
const int N = 4005;
int a[N];
int b[N];
int c[N];

int main(){

    cin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();
    for (int i = 1;i <= len1;i++){
        a[i] = s1[len1 - i] - '0';
    }
    for (int i = 1;i <= len2;i++){
        b[i] = s2[len2 - i] - '0';
    }
    for (int i = 1;i <= 2000;i++){
        for (int j = 1;j <= 2000;j++){
            c[i+j - 1] += a[i] * b[j];
            c[i + j]+=c[i + j - 1] / 10;
            c[i+j-1] %= 10;
        }
    }

    int lc = 4002;
    while(c[lc] == 0 && lc > 1){
        lc--;
    }
    for (int i = lc;i >= 1;i--){
        cout << c[i];
    }

    return 0;
}

- 高精度除法

#include <bits/stdc++.h>
using namespace std;

int a[5005], b, c[5005];
string s1;

int main(){

    cin >> s1 >> b;
    int len = s1.size();
    for (int i = 1;i <= len;i++){
        a[i] = s1[i - 1] - '0';
    }

    long long r = 0;
    for (int i = 1;i <= len;i++){
        // 拿上一次除的余数*10＋被除数当前这１位
        r = r * 10 + a[i];
        c[i] = r / b;
        r = r % b;
    }
    int lc = 1;
    while(c[lc] == 0 && lc < len){
        lc++;
    }
    for (int i = lc;i <= len;i++){
        cout << c[i];
    }
    cout << endl << r;

    return 0;
}