高精度大整数计算

两个高精度大整数相加

简单分析

​ 由于两个都是大整数，需要用数组或容器来存。具体运算就跟手算一样，各位相加留下10的余数多于10的进位，从个位开始一直重复到最高位即可，最后需要注意进位是否还多出一位来。

image-20230422092806798

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// c++代码
#include<iostream>
#include<stdio.h>
#include<string>
#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还有数则与进位加在一起
        if(i < B.size()) t += B[i];	//如果数B还有数则与进位加在一起
        c.push_back(t % 10); //10的余数为该位结果
        t /= 10; //进位
    }
    if(t) c.push_back(t); //检查是否还有进位
    return c; //返回结果
}

int main(){
    string a,b; //用字符串先接受输入 如123 注意1是最高位 3是最低位
    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');
    vector<int> c = add(A,B); //调用函数计算结果
    for(int i = c.size() - 1;i >= 0;i--)printf("%d",c[i]); // 还是还原正常的高位到低位输出
    return 0;
}

两个高精度大整数相减

简单分析

​ 同样由于两个都是大整数，需要用数组或容器来存。具体运算就跟手算一样，首先保证A要大于等于B，然后设t为借位，还是从低位到高位每次将A的各位 - B的各位 - 借位t，将其对10求余则为两数差该位的答案，再由其正负确定是否向高位借位。

image-20230422092741697

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// c++代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//比较两数大小
int 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 1; //完全相等直接返回1
    }
}
vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> c; //结果容器
    int t = 0; //借位
    for(int i = 0;i < A.size();i++){
        int temp = A[i] - t; //先将借位减去
        if(i < B.size()) temp -= B[i]; //如果B数还有数就减去
        c.push_back((temp + 10) % 10); //结果对10求余为该位答案
        if(temp >= 0)t = 0; //判断借位
        else t = 1;
    }
    while(c.size() != 1 && c.back()==0)c.pop_back(); //去除前缀0 如10-10=00只需要输出一个0

    return c;
}



int main()
{
    string a,b;
    cin>>a>>b;
    vector<int> 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 = cmp(A,B) ? sub(A,B) : sub(B,A); //保证A>=B
    if(!cmp(A,B))cout <<"-"; //如果A<B需要将结果加负号
    for(int i = C.size() - 1;i >= 0;i--)cout<<C[i]; // 还是还原正常的高位到低位输出
    return 0;
}

高精度大整数乘小整数

简单分析

​ 只有一个大整数所以只需要一个容器来存另一个用整数即可，与手算有点点区别，还是从低位到高位依次用大整数的每一位乘以小数b得到一个小整数，将其对10求余就是该位的答案并将多余的进位运算,同样注意前缀0问题;

image-20230422092649078

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// c++代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A,int b){
    vector<int> c; //存结果
    int t = 0; //进位
    for(int i = 0;i < A.size() || t;i++){ //从低位开始如果遍历完A但是依然还有进位继续循环
        if(i < A.size()) t += A[i] * b; //得到每位的总结果
        c.push_back(t%10); //对10求余得到当前位的结果
        t /= 10; //其余进位
    }
    while(c.size() != 1 && c.back() == 0)c.pop_back(); //去除前缀0 如12*0=00只要一个0  			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'); //依然倒置让个位在前
    vector<int> C = mul(A,b);  
    for(int i = C.size() - 1;i >= 0;i--)cout<<C[i]; // 还是还原正常的高位到低位输出
    return 0;
}

高精度大整数除以小整数

简单分析

​ 只有一个大整数所以只需要一个容器来存另一个用整数即可，与手算有区别，从高位开始算，将每一位加上上一位的余数*10除以b，继续将余数留给下一位，直到大数的每一位计算完，需要注意答案是从高位到低位排列的，要去除前缀0需要先逆置;

image-20230422092709367

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// c++代码
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int r;

vector<int> div(vector<int> A,int b){
    vector<int> c;
    int t=0; //上一位的余数
    for(int i = A.size() - 1;i >= 0;i--){ //除法需要从高位开始除
        int temp = t*10 + A[i];  //上一位余数因为高一位需要*10加上该位
        c.push_back(temp / b); //得到该位的答案
        t = temp % b; //将该位余数记录
    }
    r = t; //最终余数
    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');//依然倒置让个位在前
    vector<int> C = div(A,b);
    for(int i = C.size() - 1;i >=0;i--)cout<<C[i]; // 还是还原正常的高位到低位输出
    cout<<endl<<r;//输出余数
    return 0;
}