高精度加法

题目描述

给定两个正整数，计算它们的和

共两行，每行包含一个整数

输出一行，包含所求的和

数据长度$1<=N<=1000000$

问题分析

本题数据量庞大，数据长度有100W的长度，因此得将数使用字符串来存，将数字拆开后倒序存储，这样有效解决进位而要改变数组长度的问题，因此这样处理方法简单

将两个数进行逐位相加，判断进位则采用一个标识t来判断，所加和为$n_1+n_2+t$

代码实现

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

vector<int> add(vector<int> &A, vector<int> &B){
	// 定义新的容器用来存储 A + B 
	vector<int> C;
	// 定义进位,初始为 0; 
	int t = 0; 
	// 循环累加 A 与 B 的各个位的数
	for(int i = 0; i < A.size() || i < B.size(); i++ ) 
	{
		// 分别判断 A 与 B 是否还有数 
		if(i < A.size())	t += A[i];
		if(i < B.size())	t += B[i];
		// 将其个位数添加 
		C.push_back(t % 10);
		// 判断 t 是否进位，若进位则修改为 1
		t /= 10; 
	}
	// 判断最后是否进位
	if(t) C.push_back(1);
	return C; 
}

int main(){
	string a, b;
	vector<int> A, B, C;
	
	cin >> a >> b; 
	// 倒序逐个拆分数字放入 <vector> 中
	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');
	C = add(A, B);
	//	倒置输出，因为装入时倒序装入 
	for(int i = C.size() - 1; i >= 0; i--)	printf("%d" ,C[i]);
	return 0;
}

运行结果

输入

154540
2544111

输出

总结

对于大整数用字符串进行存放，拆分后的每一个数字用vector存放，从后开始往前存解决进位数字长度变化问题

循环次数取决于两个数的长度

每次动态通过t /= 10判断是否有进位

高精度减法

题目描述

给定两个正整数，计算它们的差

共两行，每行包含一个整数

输出一行，包含所求的差

数据长度$1<=N<=10^6$

问题分析

高精度减法需要判断符号问题，考虑差存在负数情况，因此优先比较两个数的大小

代码实现

#include<bits/stdc++.h>

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];
    }
    // 否则相等直接返回true
    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0; // 进位
    // 1.逐位相减
    for(int i = 0, t = 0; i < A.size(); i++) {
        // 2.判断借位
        t = A[i] - t;
        if(i < B.size())    t -= B[i];
        // 装入新数组
        // 相当于是:
        //    t < 0时, t + 10;
        //    t >= 0时, t
        C.push_back((t + 10) % 10);
        if(t < 0)   t = 1;
        else t = 0;
    }
    
    // 去前导 0 
    while(C.size() > 1 && C.back() == 0)    C.pop_back();
    return C;
    
}

int main(){
    // 两个数字，定义为字符串
    string a, b;
    // 将每一位存入 vector
    vector<int> A, B, C;
    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)){
        C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--)	printf("%d" ,C[i]);
    }
    else{
        C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--)	printf("%d" ,C[i]);
    }
        
    return 0;
}

运行结果

输入

15454
2544111

输出

-2528657

总结

优先比较两个数的大小，判断每一位的差是$>=0$还是$<0$，来决定高位的借位

高精度乘法

题目描述

给定两个正整数A和B，计算$A*B$的值

共两行，每行包含一个整数

输出一行，包含$A*B$的值

数据长度：

$1<=A<=10^6$

$1<=B<=10^4$

问题分析

高精度乘法这里采用一个实例进行分析

设$A * b = C$

代码实现

#include<bits/stdc++.h>

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++ ){
        if(i < A.size())    t += A[i] * b;  // 进位+两数相乘结果
        C.push_back(t % 10);    // 当前位取结果的余
        t /= 10;    // 进位取结果的整除值
    }
    return C;
}

int main(){
    string a;
    int b;
    // 将每一位存入 vector
    vector<int> A;
    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;
}

运行结果

输入

31442
245

输出

总结

高精度的乘法需要考虑到进位的问题，有些类似与高精度加法，只是每次相乘将$b$看成一个整体，分别与$A$的每一位相乘

高精度除法

题目描述

给定两个正整数A和B，计算$A / B$的值

共两行，每行包含一个整数

输出一行，包含$A/B$的值

数据长度：

$1<=A<=10^6$

$1<=B<=10^4$

问题分析

高精度除法与其他三种运算方式不同，它是先计算高位，因此首先操作高位。

代码实现

#include<bits/stdc++.h>

using namespace std;

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 --){
        // 每次b要除的数
        r = r *10 + A[i];
        C.push_back(r / b); // 取整除部分
        r %= b; // 取余下部分
    }
    // 由于取的时候是从末尾开始取的，因此逆序，将其反转
    reverse(C.begin(), C.end());
    // 去除前导0
    while(C.size() > 1 && C.back() == 0)    C.pop_back();
    return C;
}

int main(){
    string a;
    int b;
    // 将每一位存入 vector
    vector<int> A;
    cin >> a >> b;
	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 << r << endl;
    
    return 0;
}

运行结果

输入

9654
21

输出

459
15

总结

高精度的除法需要考虑每一位的存储问题，因为他不同的是先运算的是高位，其次是低位，因此为了统一操作，除法仍然选择相同的方式存储，在运算得到的新数组里通过逆序，使其保持输出一致