C++之高精度详解

微信扫一扫,分享到朋友圈

C++之高精度详解

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

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

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

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

  • 1.高精度加法

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

代码:

#include 
#include 
#include 
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;ilb?la:lb;//选择位数较多的作为目前相加后的位数,之后可能会以后进位 
  for(register int i=1;i1) lc--;//除去前导0 
  for(register int i=lc;i>=1;i--) cout<<sum[i];
  return 0;
}
  • 2.高精度减法

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

代码:

#include 
#include 
#include 
#include 
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]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 
#include 
#include 
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;j1) lc--;
  for(register int i=lc;i>=1;i--) cout<<mult[i];
  return 0;
}
  • 4.高精度除法

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

(1)高除低

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

代码:

#include 
#include 
#include 
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 
#include 
#include 
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;ib[0]) return 1;
  if(a[0]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]=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;
}

参考与引用:

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

本人喜爱诗句分享赏析:

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

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

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

微信扫一扫,分享到朋友圈

C++之高精度详解

Create an Extended Date Dimension for a SQL Server Data Warehouse

上一篇

高通835+3K屏,Pico G2 VR一体机售价1999元,8月1日正式发售

下一篇

你也可能喜欢

C++之高精度详解

长按储存图像,分享给朋友