C++中高精度运算总结

2022-05-05 09:03:54

一.产生原因

二.不同方法介绍

一.产生原因

首先明确为什么有高精度运算即大数的运算。由于C++中最大的long long也只能存到2^63-1=9223372036854775807（19位数），但当数字长度接近10^5甚至更长时就没办法用long long储存了，所以不能直接对变量进行加减，因此有了高精度算法，最近我刚学，怕忘就总结了一下，仅供参考，如有错误还请指正。

对了：题目指路

加法：https://www.acwing.com/problem/content/793/

减法：https://www.acwing.com/problem/content/794/

乘法：https://www.acwing.com/problem/content/795/

除法：https://www.acwing.com/problem/content/796/

二.不同方法介绍

高精度算法一般有两种形式，①数组模拟 ②用STL中的vector容器。

①：将字符串string中的每一位转化为int数组中的数；

②：用vector中

的函数push_back(); pop_back(); back(); front(); begin(); 进行操作；

两者的模拟加法的大致思想是一样的，但STL容器可以在空间上随用随申请，而数组只能提前申请（a[100010]）固定空间。

三.模拟过程（核心代码）

1.加法（进位）

这个是平时咱们计算的过程（红1表示进位）而写程序时咱们需要找到一个循环起来的方法，于是继续思考我们为什么会知道进位以及进多少

上图为直接对每一位相加之后的结果，从最低位（个位）看起，就可以发现8=18%10,9=（18+1）%10，1=（0+1）%10。这样就找到规律了：

每一位上的数字=（进位+加数上同位两数字的和）%10

进位=（进位+加数上同位两数字的和）/10

注：这里是默认的a的长度>b的长度！

（数组模拟，rr[]为结果）

for(int i=0; i<len; i++)//len为aa,bb两个数字的长度的最大的一个
{
    rr[i]=aa[i]+bb[i];
}
for(int i=0; i<len; i++)
{
    if(rr[i]>=10)  rr[i+1]++,rr[i]-=10;
}
if(rr[len])  len++;//这里处理a+b后最高位的进位问题

注：这里一定要分两个for来加和判断，要不然循环第二次进行时会覆盖++，进位就没有用到！

等等，写到这里我突然意识到只要把res那改成+=就可以了！妙蛙！

for(int i=0; i<len; i++)
{
    rr[i]+=aa[i]+bb[i];
    if(rr[i]>=10)  rr[i+1]++,rr[i]-=10;
}

（vector）

for(int i=0; i<a.size()+1; i++)//这里size+1是防止长度增加的进位
{
    t+=a[i];
    if(i<b.size())  t+=b[i];
    //这里分成两部分加是为了防止vector越界，数组不用是因为设置全局数组后有默认值0

    res.push_back(t%10);
    t/=10;
}

2.减法（借位）

从结果上来看a-b可能是正数可能是负数，负数时加上符号变成b-a即可，这里不再赘述。

比较简单的情况是被减数的每一位都恰好比减数的每一位大，这里就不列举了；

比较复杂的就是下图这样有借位的情况：

还是和加法一样先对每一位做减法（红字），然后从低位（个位）开始考虑借位变成下图（蓝字）

就可以找到规律：

每一位上的数字=同位减法，判断是否<0，小于则下一位（高位）--，本位+=10

Or:

每位数字=（同位减法+10-标记）%10，如果减法<0则标记1，否则标记0

（这个标记是在下一位（高位）时才开始起作用，模拟借位的过程，先判断有没有被借过位）

注：这里默认a>b！

（数组）

for(int i=0; i<lena; i++)  
    rr[i]=aa[i]-bb[i];
for(int i=0; i<lena; i++) 
    if(rr[i]<0)  rr[i]+=10,rr[i+1]--;

有了加法的启示这里也可以改良一下

for(int i=0; i<lena; i++)
{
    rr[i]+=aa[i]-bb[i];
    if(rr[i]<0)  rr[i]+=10,rr[i+1]--;
}

（vector）

for(int i=0; i<a.size(); i++)
{
    t=a[i]-t;
    if(i<b.size())  t-=b[i];//和加法同理

    res.push_back((t+10)%10);
 
    if(t<0)  t=1;
    else  t=0;
}

3.乘法（高精度a*低精度b）

数组模拟法的难点在于一个公式的理解：

res[i+j]=a[i]*b[j]

这里我想了一个神奇的例子，希望可以帮助理解：

结果中res[7]=6，乘数中a[2]=2，b[5]=3，从这里我们可以看出res[2+5]=a[2]*b[5]，规律立现！

容器法就相对简单一点，直接暴力每一位都乘一遍b，取模作为这一位上的结果，其实和加法类似。

每一位数字=(a[i]*b+jw)%10；

进位+=(a[i]*b+jw)/10;

（数组）

for(int i=0; i<lena; i++)
{
    int jw=0;//进位
    for(int j=0; j<lenb; j++)
    {
        rr[i+j]+=aa[i]*bb[j]+jw; 
        jw=rr[i+j]/10;
        rr[i+j]%=10;
    }
    rr[i+lenb]=jw;//两位数乘一位数得到三位数的情况
}

（vector）

vec mul(vec &a,int b)
{
    vec res;
    int t=0;

    for(int i=0; i<a.size() || t; i++)
    {
        if(i<a.size())  t+=a[i]*b;
        res.push_back(t%10);
        t/=10;
    }
}

4.除法（高精度a÷低精度b）

首先1/31=0,

（1*10+2）/31=0，（（1*10+2）*10+0）/31=3 ，得到余数27，模拟完过程就可以找到规律了！

每位数字=（上一位的余数*10+本位）/除数

余数=（上一位的余数*10+本位）-除数*结果位数字

由于除法的力量过于玄学，此处就只放vector版本了。

r=0;//余数要有初始值0
for(int i=a.size()-1; i>=0; i--)//从高位除起，所以后续不需要reverse
{
    r=r*10+a[i];
    res.push_back(r/b);
    r%=b;
}

四.完整代码

篇幅有限，我就不介绍一些细节比如去除前导0了，我会在代码中注释一下。

1.加法

#include <iostream>
#include <cstring>
#define N 10010
using namespace std;

char a[N],b[N],res[N];
int aa[N],bb[N],rr[N];
int lena,lenb;

int main()
{
    scanf("%s",a);
    scanf("%s",b);

    int lena=strlen(a),lenb=strlen(b);
    int len=max(lena,lenb);

    for(int i=0; i<lena; i++)  aa[i]=a[lena-i-1]-'0';//先逆序存到int数组里方便处理
    for(int i=0; i<lenb; i++)  bb[i]=b[lenb-i-1]-'0';
    //为啥要逆序呢，为了让长度不等的两个独立对象右对齐

    for(int i=0; i<len; i++)
    {
        rr[i]+=aa[i]+bb[i];
        if(rr[i]>=10)  rr[i+1]++,rr[i]-=10;
    }

    if(rr[len])  len++;//多进一位的情况，比如99+1=100
    
    for(int i=len-1; i>=0; i--)   printf("%d",rr[i]);
}

2.减法

#include <iostream>
#include <cstring>
#define N 10010
using namespace std;

char a[N],b[N];
int aa[N],bb[N],rr[N];
int lena,lenb;
bool flag=true;

int cmp()//a>b->1   a<b->-1  a==b->0
{
    lena=strlen(a);
    lenb=strlen(b);
    if(lena>lenb)  return 1;
    else if(lena<lenb)  return -1;
    else  return strcmp(a,b);
}

int main()
{
    while(scanf("%s%s",a,b)!=2)//万一只有一个输入值
    {
        cout<<a;
        return 0;
    }
    if(cmp()==0)
    {
        cout<<0;
        return 0;
    }
    else if(cmp()<0)  swap(a,b),swap(lena,lenb), cout<<"-";//b-a->a-b
    for(int i=0; i<lena; i++)  aa[i]=a[lena-i-1]-'0';
    for(int i=0; i<lenb; i++)  bb[i]=b[lenb-i-1]-'0';

    for(int i=0; i<lena; i++)
    {
        rr[i]+=aa[i]-bb[i]; 
        if(rr[i]<0)  rr[i]+=10,rr[i+1]--;
    }

    int i=lena-1;
    while(!rr[i])  i--;//去除前导0
    for(; i>=0; i--)  printf("%d",rr[i]);
}

3.乘法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<int> vec;

vec mul(vec &a,int b)
{
    vec res;
    int t=0;

    for(int i=0; i<a.size() || t; i++)
    {
        if(i<a.size())  t+=a[i]*b;//用if防止i越界，vector与数组不一样在于不会默认补0
        res.push_back(t%10);
        t/=10;
    }

    while(res.size()>1 && res.back()==0)  res.pop_back();//去除前导0（现在还在0最后面）
    reverse(res.begin(),res.end());

    return res;
}

int main()
{
    string a;
    int b;
    vec aa,rr;
    cin>>a>>b;

    for(int i=a.size()-1; i>=0; i--)  aa.push_back(a[i]-'0');
    rr=mul(aa,b);

    for(int i=0; i<rr.size(); i++)  printf("%d",rr[i]);
}

4.除法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<int> vec;

int r;

vec div(vec &a,int b)
{
    vec res;
    r=0;

    for(int i=a.size()-1; i>=0; i--)//从高位除起，所以后续不需要reverse
    {
        r=r*10+a[i];
        res.push_back(r/b);
        r%=b;
    }

    while(res.size()>1 && res.front()==0)  res.erase(res.begin());//delete 0

    return res;
}

int main()
{
    string a;
    int b;
    vec aa,rr;
    cin>>a>>b;

    for(int i=a.size()-1; i>=0; i--)  aa.push_back(a[i]-'0');
    rr=div(aa,b);

    for(int i=0; i<rr.size(); i++)  printf("%d",rr[i]);
    cout<<endl<<r;
}

码农公寓

一.产生原因

二.不同方法介绍

三.模拟过程（核心代码）

1.加法（进位）

2.减法（借位）

3.乘法（高精度a*低精度b）

4.除法（高精度a÷低精度b）

四.完整代码

1.加法

2.减法

3.乘法

4.除法

相关文章