关于程序员:算法基础之高精度总结

高精度算法分类

分类：加、减、乘、除

其中加减乘都实用于两个数都是高精度，除法因为除数是高精度的话不好用整除的办法，所以除法时被除数是高精度，除数是整型。

高精度加减乘除的异同点

加和乘

相同点

1. 须要 从低位到高位解决

   for(int i=stra.size()-1;i>=0;i--) c.push_back(stra[i]-'0');

2. 加和乘 解决向上进位

   int t=0;
   for(...){t += a[i];
    c.push_back(t % 10);
    t /= 10;
   }

3. 能够应用 通用模板

   加法

   c[i]+=a[i];
   c[i]+=b[i];
   // 而后对立对 c 进行进位解决

乘法

c[i+j] = a[i]*b[j];
// 而后对立对 c 进行进位解决

减和除

相同点

1. 有可能以后位的数不够，须要 借用上一位

不同点

1. 减法须要从低位到高位解决，除法是从高位到低位解决

2. 减法每一位都要解决上一位的 借位 状况，借位要么是 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;
   
   }

3. 除法更多的应该是叫 凑位，把高位的数 *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 多平台公布