高精度加减法(超详细)
题目1-高精度加法
给定两个正整数(不含前导 0),计算它们的和。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的和。
数据范围
1≤整数长度≤100000
输入样例:
12
23
输出样例:
35
#include<iostream>
#include<vector>
#include<cstring>
#include<vector>
using namespace std;
vector<int> add(vector<int> A, vector<int> B){
//这一步是必须的,需要判断数组A和数组B哪一个位数更多,作为下面for循环的结束条件。
if(A.size()<B.size()) return add(B,A);
vector<int> C;
int tmp = 0; //tmp用来保存进位
for(int i=0; i<A.size();i++ ){
tmp += A[i];
//这一步的if判断也是必须的,需要对短的那个数组进行判断,确保便利的时候不会越界。
if(i<B.size()) tmp += B[i];
C.push_back(tmp%10);
tmp = tmp/10;
}
if(tmp==1) C.push_back(1); //如果加完之后c任然有数,代表两个数组位数相等且有进位的极端情况。
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');
auto C = add(A,B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
}
算法思想:相当于自己模拟了一次加法的过程:
//1、vector数组更方便于存储大整数并且对其进行操作。
//2.注意在模拟加法时对进位c的是如何处理的,以及在模拟过程中一些看似不重要但是确实必是不可少的一些细节。
需要注意以下几点:
1.计算的时候需要把大的数放在前面,方便后面作为循环终止的条件。
2.在处理进位tmp的时候要特别小心处理,如果加完之后c仍然有数需要加到新的数组中(是两个数组位数相等且有进位的情况).
3.在C++中,push_back()是一个成员函数,它用于向vector容器的末尾添加一个元素。vector是一种动态数组,可以动态地增加和减少元素。push_back()函数会在vector的末尾添加一个新元素,如果必要的话,它会重新分配内存以容纳更多的元素。
题目2 高精度减法
给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的差。
数据范围
1≤整数长度≤105
输入样例:
32
11
输出样例:
21
//算法思想:减法比加法更加复杂,多了一步两个数的比较,在处理进位的时候也不同。
#include<iostream>
#include<vector>
using namespace std;
bool 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 true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
//t代表进位,如果t为复数则上一位多减1,整数t=0.
vector<int> C;
int t=0;
for(int i=0;i<=A.size()-1;i++){
t=A[i]-t;
if(i<B.size()) t=t-B[i];
C.push_back((t+10)%10);//将t>0和t<0两种情况都包括了。
if(t<0) t=1;
else t=0;
}
//最后检查是否会有0004的情况。注意这里还是逆序,0004对应4000
for(int i=0;i<C.size();i++) cout<<C[i]<<endl;
while(C.size()>1 && C.back()==0) C.pop_back();
return C;
}
int main(){
string a,b;
cin>>a>>b;
vector<int> A,B;
vector<int> C;
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=sub(A,B);
if(cmp(A,B)){
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}
else{
C=sub(B,A);
//在这里输出的时候要先输出一个负号
cout<<'-';
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}
return 0;
}
算法思想:减法要保证大的数在前面计算,如果A>=B,则计算A-B;如果A<B,则计算-(B-A).。
本文含有隐藏内容,请 开通VIP 后查看