高精度算法分类
分类：加、减、乘、除
其中加减乘都适用于两个数都是高精度，除法因为除数是高精度的话不好用整除的方法，所以除法时被除数是高精度，除数是整型。
高精度加减乘除的异同点
加和乘
相同点
- 需要从低位到高位处理
for(int i=stra.size()-1;i>=0;i--) c.push_back(stra[i]-'0');
- 加和乘处理向上进位
int t=0;
for(...){
t += a[i];
c.push_back(t % 10);
t /= 10;
}
- 可以使用通用模板
加法
c[i]+=a[i];
c[i]+=b[i];
//然后统一对c进行进位处理
乘法
c[i+j] = a[i]*b[j];
//然后统一对c进行进位处理
减和除
相同点
- 有可能当前位的数不够，需要借用上一位
不同点
-
减法需要从低位到高位处理，除法是从高位到低位处理
-
减法每一位都要处理上一位的借位情况，借位要么是0要么是1
int t=0;
//注意：a是从低位到高位排序
for(int i=0;i<a.size();i++){
t = a[i]-t;
if(i<b.size()) t -= b[i];
c.push_back(t % 10);
//下一位的借位
if(t <0) t=1;
else t = 0;
}
- 除法更多的应该是叫凑位，把高位的数*10和低位的数合并，每个位置不需要再单独加减
int r=0; //余数
//注意a是从高位到低位排序
for(int i=0;i<a.size();i++){
r = r * 10+a[i];
c.push_back(r /b);
r = r % b;
}
4.除法处理前导0的情况需要翻转，把高位翻转到末尾
reverse(c.begin(),c.end());
处理前导0的方式
四种运算都一样，只是除法先要翻转数组
while(c.size()>1 && c.back()==0) c.pop_back();
本文由mdnice多平台发布