C++之高精度详解

NOIP2018即将到来，现在在刷题的同时，也不应该忘记巩固基础知识。

于是今天来水一波高精度。

高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。

高精度运算的思路即为： 用字符串读入数字，之后倒序转成数字，在循环中模拟加减乘除的过程。

• 1.高精度加法

题目链接： https://www.luogu.org/problemnew/show/P1601

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int la,lb,lc,temp,c[10001],d[10001],sum[10001];
char a[10001],b[10001];
int main()
{
  cin>>a>>b;
  la=strlen(a);
  lb=strlen(b);
  for(register int i=0;i<la;i++) c[la-i]=a[i]-'0';//倒序转到另一个数组 
  for(register int i=0;i<lb;i++) d[lb-i]=b[i]-'0';
  lc=la>lb?la:lb;//选择位数较多的作为目前相加后的位数，之后可能会以后进位 
  for(register int i=1;i<=lc;i++)
  {
    sum[i]=c[i]+d[i]+temp;
    temp=sum[i]/10;//进位 
    sum[i]%=10;
  }
  sum[++lc]=temp;//把最后剩的进位储存 
  while(sum[lc]==0&&lc>1) lc--;//除去前导0 
  for(register int i=lc;i>=1;i--) cout<<sum[i];
  return 0;
}

• 2.高精度减法

题目链接： https://www.luogu.org/problemnew/show/P2142

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;
long long la,lb,c[100001],d[100001],sub[100001];
char a[100001],b[100001];
int main()
{
  cin>>a>>b;
  if(strlen(a)<strlen(b)||(strlen(a)==strlen(b)&&strcmp(a,b)<0))
    {
        cout<<"-";
        swap(a,b);
    }//比较两个数的大小：若a的长度小于b的长度或位数相同但是a<b，则交换两个数 
  la=strlen(a);
  lb=strlen(b);
  for(register int i=0;i<la;i++) c[la-i]=a[i]-'0';//同上 
  for(register int i=0;i<lb;i++) d[lb-i]=b[i]-'0';
  for(register int i=1;i<=la;i++)
  {
    if(c[i]<d[i])
    {
      c[i+1]--;//借位 
      c[i]+=10;
    }
    sub[i]+=c[i]-d[i];
  }
  while(sub[la]==0&&la>1) la--;//除去前导0 
  for(register long long i=la;i>=1;i--) cout<<sub[i];
  return 0;
}

• 3.高精度乘法

题目链接： https://www.luogu.org/problemnew/show/P1303

与加减不同的地方，乘除法是 用一个数的某一位乘或除另一个数的所有位。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char a[10001],b[10001];
int la,lb,lc,x,c[10001],d[10001],mult[10001]; 
int main()
{
  cin>>a>>b;
  la=strlen(a);
  lb=strlen(b);
  for(register int i=0;i<la;i++) c[la-i]=a[i]-'0';
  for(register int i=0;i<lb;i++) d[lb-i]=b[i]-'0';
  for(register int i=1;i<=la;i++)
  {
    x=0;
    for(register int j=1;j<=lb;j++)
    	{
    		mult[i+j-1]+=c[i]*d[j]+x;//一个数a乘以另一个数b，在有进位的情况下，积的位数是strlen(a)+strlen(b)-1。 
    		x=mult[i+j-1]/10;//进位，与加法类似 
    		mult[i+j-1]%=10;
    	}
    	mult[i+lb]=x;//进位 
  }
  lc=la+lb;
  while(mult[lc]==0&&lc>1) lc--;
  for(register int i=lc;i>=1;i--) cout<<mult[i];
  return 0;
}

• 4.高精度除法

高精度除法是在高精度运算中较麻烦的，我们有两种实现的方式。一是 按位相除 ，二是 循环减法 。我会分别详解 高精度除以低精度 和 高精度除以高精度 。

（1）高除低

我们使用按位相除的方法会更加方便。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char a[10001];
int la,lc,x,b,c[10001],div[10001];
int main()
{
  cin>>a>>b;
  la=strlen(a);
  for(register int i=0;i<la;i++) c[i+1]=a[i]-'0';//在这里不需倒序存储，我们只需要把a转成数字 
  for(register int i=1;i<=la;i++)//按位相除 
  {
    div[i]=(x*10+c[i])/b;
    x=(x*10+c[i])%b;
  }
  lc=1;
  while(lc<la&&div[lc]==0) lc++;
  for(register int i=lc;i<=la;i++) cout<<div[i];//正序输出结果即可 
  return 0;
}

（2）高除高，求其商和余数

我们使用减法模拟除法，对被除数的每一位都减去除数，一直到当前位置的数小于除数。循环次数很小，只会在10以内。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int flag,a[10001],b[10001],c[10001],temp[10001];
inline void init(int *a)//利用位置 
{
  string s;
  cin>>s;
  a[0]=s.length();//用string类型读入获取长度 
  for(register int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';//转换 
}
inline void numcpy(int *p,int *q,int pos)//copy p数组到q数组从pos开始的地方 
{
  for(register int i=1;i<=p[0];i++) q[i+pos-1]=p[i];
  q[0]=p[0]+pos-1;
}
inline int compare(int *a,int *b)//比较两个数大小 
{
  if(a[0]>b[0]) return 1;
  if(a[0]<b[0]) return -1;
  for(register int i=a[0];i;i--)
  {
    if(a[i]>b[i]) return 1;
    if(a[i]<b[i]) return -1;
  }
  return 0;
}
inline void sub(int *a,int *b)//相减 
{
  flag=compare(a,b);
  if(flag==0)//若位数相同则刚好减完 
  {
    a[0]=0;
    return;
  }
  else if(flag==1)
  {
    for(register int i=1;i<=a[0];i++)
    {
      if(a[i]<b[i])
      {
        a[i+1]-=1;
        a[i]+=10;
      }
      a[i]-=b[i];//模拟减法过程 
    }
    while(a[a[0]]==0&&a[0]) a[0]--;
    return ;
  }
}
int main()
{
  init(a);
  init(b);
  c[0]=a[0]-b[0]+1;//计算长度 
  for(register int i=c[0];i;i--)
  {
    memset(temp,0,sizeof(temp));//清零 
    numcpy(b,temp,i);
    while(compare(a,temp)>=0)
    {
      c[i]++;//商 
      sub(a,temp);
    }
  }
  while(c[c[0]]==0&&c[0]) c[0]--;
  if(c[0]==0) cout<<"0";
  else for(register int i=c[0];i;i--) cout<<c[i];
  cout<<endl;
  if(a[0]==0) cout<<"0";
  else for(register int i=a[0];i;i--) cout<<a[i];//输出余数 
  return 0;
}

参考与引用：

《信息学奥赛一本通》第四版  高精度计算

本人喜爱诗句分享赏析：

• 花有重开日，人无再少年。——陈著 《续侄溥赏酴醾劝酒二首其一》

花儿即使凋谢，第二年又能再次盛开，而人却不同，过一天就少一天，少年时光一去不复返啊！

这句话经常出现在元曲的开头。现今很适合像我们一样正处少年时期的学生。不应浪费青春。