1 大整数存储
将个位存到数组的第一位(原因:可能需要进位 直接push_back)
2 大整数运算(模拟人工运算)
高精度加法
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int> A,B,C;
vector <int> add (vector<int>& A,vector<int>& B){//加引用的原因:提高效率
//不加引用 会将这个数组copy一遍 不加引用的的话就不用copy 快很多
int t=0;//用t来处理进位
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size()) t+=A[i];//注意两个if必须写 否则会数组越界
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t>0) C.push_back(t);
return C;
}
int main(){
string a,b;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)//注意a.size()的-1 否则会导致未知错误 A.push_back(a[i]-'0');//必须减'0' 存入的是ascll码
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;
}
注意:
1 注意a.size()的-1 否则数组可能越界 会导致未知错误
2 不减‘0’的结果
例如如下代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int> A,B,C;
int main(){
string a;
cin>>a;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]);
for(int i=0;i<=a.size()-1;i++) printf("%d",A[i]);
return 0;
}
输入012
我们想要它输出210
实际输出:504948
3 引用
int& p=a;
定义了一个 p 和 a 存在一个地址上 当改变p的时候,a也跟着改变
高精度减法
思路:
A[i]-B[i]-t
=0 不用借位 C[i]=A[i]-B[i]-t
<0 要借位 C[i]=A[i]-B[i]-t+10
用t来存储A-B-t的结果
第一步:t暂存A[i] 计算A[i]-t的结果
第二步:计算A[i]-B[i]-t
即
t>=0 不用借位 C[i]=t
t<0 要借位 C[i]=t+10
这一步可以用(t+10)%10 来合并
还需要处理结果可能为负
只需交换A,B,然后在前面加负号
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int> C;
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){
int t=0;
for(int i=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size()) t-=B[i];
C.push_back((t+10)%10);
if(t>=0) t=0;
else t=1;
}
while(C.size()>1&&C.back()==0) C.pop_back();//如果结果不是一位数(排除0) 并且C后面有0的话 把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');
if(cmp(A,B)) C=sub(A,B);
else {
C=sub(B,A);
cout<<'-';
}
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl;
return 0;
}
大整数乘法
A*b(b为int)
把b当作一个整体 分别和A的每一位乘
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#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>0;i++){//直接把需要进位的代码合并
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();//注意处理前导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;
}
也可以写成和加法一样
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#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();i++){
t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);//一定注意乘法这里补上的是t 不是1
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=mul(A,b);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}
高精度除法
eg:
A3 A2 A1 A0
7 6 5 4 ÷2—b余数r=A3
C3=r/b
r1=r%bC2=(r1×10+A2)/ b
r2=(r1×10+A2)% b
注意两处翻转:
第一次:div函数中for循环条件
第二次:reverse函数
(本质上不倒着存更简化 但由于通常四则运算混着一起,所以用和加减乘一样的存储方式,进行两处翻转)
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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--){//注意循环顺序不同
r=r*10+A[i];
C.push_back(r/b);//注意是b 容易写成10
r%=b;//注意是b 容易写成10
}
reverse(C.begin(),C.end());//注意翻转
while(C.size()>1&&C.back()==0) C.pop_back();//去掉前导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');
int r;
vector<int> C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl<<r<<endl;
return 0;
}