算法基础之高精度总结

Praguelove / 85 / 2023-09-24 21:09:34

ChatGPT 可用网址,仅供交流学习使用,如对您有所帮助,请收藏并推荐给需要的朋友。
https://ckai.xyz

高精度算法分类

分类:加、减、乘、除

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

高精度加减乘除的异同点

加和乘

相同点

  1. 需要从低位到高位处理

    for(int i=stra.size()-1;i>=0;i--) c.push_back(stra[i]-'0');
  1. 加和乘处理向上进位

    int t=0;
    for(...){
     t += a[i];
     c.push_back(t % 10);
     t /= 10;
    }
  2. 可以使用通用模板

    加法
    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;
    
    }
  1. 除法更多的应该是叫凑位,把高位的数*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多平台发布


作者
Praguelove
许可协议
CC BY 4.0
发布于
2023-09-24
修改于
2024-05-27
Bonnie image
尚未登录