一、高精度加法
? ? ? ? 主要思想：通过把较大的数按位依次保存在数组里，实现大数的相加。实际操作中为了方便进位，保存时要采用小端法，从个位开始存储，即存储数7654时，a[0]存4,a[1]存5，a[2]存6，a[3]存7，倒序进行存储。定义t保存进位，从个位开始依次相加，最终运算结果的每一位的值都是A[i]+B[i]+t。结果输出时再倒序遍历数组进行输出。
? ? ? ?
????????例题：两个特别大的数A和B求和。
#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B){//对数组进行引用不需要拷贝，节省时间
int t=0;//t中存储进位
vector<int> C;
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);//保存相加结果的个位
t/=10;//t更新为进位
}
if(t) C.push_back(1);//最高位还有进位要补1
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');//实现ASCLL码到数字的转换
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');//必须是单引号，双引号是字符组，不能相减
auto C=add(A,B);//auto为计算机自己判断类型，也可以写成vector<int>
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
????????注1：重点关注几个遍历中的顺序，读入数组是逆序，相加计算是顺序，输出结果是逆序。
? ? ? ? 注2：vector是向量类型，可以容纳许多类型的数据，因此也被称为容器，尖括号内是数据类型，添加元素用类函数push_back()，读取元素类数组可以直接用下标。
二、高精度减法
? ? ? ? 主要思想：存储和输出与大数相加相同，减法运算时定义t存储借位，当A[i]-B[i]-t<0时不够减，借1位加上10，结果存为A[i]-B[i]-t+10的个位，t更新为1；当A[i]-B[i]-t>=0时够减，结果存为A[i]-B[i]-t的个位，t更新为0。输出时还要考虑多余的0，确保不会出现"000"、“001”等情况。
? ? ? ? 例题：两个特别大的数A和B求差。
#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B){//自定义cmp函数比较A和B的大小
if(A.size()!=B.size()) return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--){//【1】
if(A[i]!=B[i]) return A[i]>B[i];
}
return true;//遍历完还没有返回，A=B
}
vector<int> sub(vector<int> &A,vector<int> &B){
int t=0;//t存储借位
vector<int> C;
for(int i=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size()) t-=B[i];//当B还没有遍历完才减
C.push_back((t+10)%10);//合并t>=0和t<0的两种处理情况
if(t>=0) t=0;//够减，不用借位
else t=1;//不够减，借位1
}
while(C.size()>1&&C.back()==0) C.pop_back();
//处理冗余的0，C的最后一个值即为结果的最高位
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');
if(cmp(A,B)){//当A>=B时直接减
auto C=sub(A,B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}
else{//A<B时计算B-A再添负号
auto C=sub(B,A);
printf("-");
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);//【2】
}
return 0;
}
? ? ? ? 【1】：A和B位数相同时，比较第一个不相等的数的大小来确定A和B的大小。注意数组内是逆序存储，比较时要从高位依次向后比较，逆序遍历。
????????【2】：虽然不论A-B还是B-A，输出C的方式相同，但只能把输出写在if-else内，写到外面编译器识别不到C的定义会报错。
三、高精度乘法
? ? ? ? 主要思想：按照多位数乘个位数的计算方式，把小数b当成个位数进行乘法运算。从个位开始遍历大数A的每一位A[i]，依次与小数b进行乘法运算，最终结果C的每一位C[i]都是每次乘法运算的结果模10，进位是每次乘法运算的结果除以10。
? ? ? ? 例题：求一个很大的数a乘一个很小的数b。
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;//t存储进位
for(int i=0;i<A.size()||t;i++){//A中还有数没计算或者进位t不为0
if(i<A.size()) t+=A[i]*b;//只有A中还有数没计算时才做乘法，注意是+=
C.push_back(t%10);
t/=10;//储存进位
}
return C;
}
int main(){
vector<int> A;
string a;
int b;
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;
}
四、高精度除法
? ? ? ? 主要思想：从大数的最高位开始依次做除法，每次除法商保留除以b的值，进位为余数乘以10。
? ? ? ? 例题：求一个很大的数除以一个小数的商和余数。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r){//r保存余数
vector<int> C;
for(int i=A.size()-1;i>=0;i--){//【1】
r=r*10+A[i];
C.push_back(r/b);
r%=b;//注意进位为模b
}
reverse(C.begin(),C.end());//C中的结果是大端存储，逆序方便后面输出
while(C.size()>1&&C.back()==0) C.pop_back();//此处是pop_back，先逆序再除冗余0
return C;
}
int main(){
vector<int> A;
string a;
int b;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
int r=0;
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;
}
? ? ? ? 【1】：注意除法运算时是从最高位开始计算，但是为了与加法减法乘法统一，便于综合计算，存储时还是用小端法（即从最低位开始存储），计算时要逆序遍历，C中的结果是大端存储，再调用reverse（）函数将结果转成小端存储，便于输出。
|