高精度算法-白红宇

高精度算法

阅读量：4502 次

发布时间：2019-06-08

本文共 4818 字，大约阅读时间需要 16 分钟。

博客内容整理自

对于大数，我们会开一个数组来储存，数组的第一位储存这个数的位数，后面倒叙存储。

高精度数的储存

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=100;int a[MAXN+1];string s;int main(){    cin>>s;    memset(a,0,sizeof(a));    a[0]=s.length();    for(int i=1;i<=a[0];i++)    {        a[i]=s[a[0]-i]-'0';    }    return 0;}

高精度数的比较

int compare(int a[],int b[]) //a>b为1，a
    
     b[0]) return 1;    if(a[0]
     
      0;i--)    {        if(a[i]>b[i]) return 1;        if(a[i]

高精度加法

void plush(int a[],int b[]){    int k;    if(a[0]>b[0]) k=a[0];    else k=b[0];    for(int i=1;i<=k;i++)    {        a[i+1]=a[i+1]+(a[i]+b[i])/10;        a[i]=(a[i]+b[i])%10;    }    if(a[k+1]>0) a[0]=k+1;    else a[0]=k;}

模板题

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 200using namespace std;string s1,s2;int a[MAXN+1],b[MAXN+1];void plush(int a[],int b[]){    int k;    if(a[0]>b[0]) k=a[0];    else k=b[0];    for(int i=1;i<=k;i++)    {        a[i+1]=a[i+1]+(a[i]+b[i])/10;        a[i]=(a[i]+b[i])%10;    }    if(a[k+1]>0) a[0]=k+1;    else a[0]=k;}int main(){    cin>>s1>>s2;    a[0]=s1.length();    b[0]=s2.length();    for(int i=1;i<=a[0];i++)    {        a[i]=s1[a[0]-i]-'0';    }    for(int i=1;i<=b[0];i++)    {        b[i]=s2[b[0]-i]-'0';    }        plush(a,b);    for(int i=a[0];i>0;i--)    {        printf("%d",a[i]);    } }

高精度减法

int gminus(int a[],int b[]){    int flag;    flag=compare(a,b);    if(flag==0)    {        memset(a,0,sizeof(a));        a[0]=1;        return 0;    }    if(flag==1)    {        for(int i=1;i<=a[0];i++)        {            if(a[i]

模板题链接

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 1000010using namespace std;string s1,s2;int a[MAXN+1],b[MAXN+1];int compare(int a[],int b[]){    if(a[0]>b[0]) return 1;    if(a[0]
         
          0;i--) { if(a[i]>b[i]) return 1; if(b[i]>a[i]) return -1; } return 0;} int gminus(int a[],int b[]){ int flag; flag=compare(a,b); if(flag==0) { memset(a,0,sizeof(a)); a[0]=1; return 0; } if(flag==1) { for(int i=1;i<=a[0];i++) { if(a[i]
          
           >s1>>s2; a[0]=s1.length(); b[0]=s2.length(); for(int i=1;i<=a[0];i++) { a[i]=s1[a[0]-i]-'0'; } for(int i=1;i<=b[0];i++) { b[i]=s2[b[0]-i]-'0'; } int chos; chos=gminus(a,b); if(chos==0) { for(int i=a[0];i>0;i--) { printf("%d",a[i]); } } else if(chos==-1) { cout<<"-"; for(int i=a[0];i>0;i--) { printf("%d",a[i]); } }}

高精度乘单精度数

void multi(int a[],ll key){    if(key==0)    {        memset(a,0,sizeof(a));        a[0]=1;        return 0;    }    for(int i=1;i<=a[0];i++)    {        a[i]=a[i]*key;    }    for(int i=1;i<=a[0];i++)    {        a[i+1]=a[i+1]+a[i]/10;        a[i]=a[i]%10;    }    k=a[0]+1;    while(a[k]>0)    {        a[k+1]=a[k+1]+a[k]/10;        a[k]=a[k]%10;        k++;        a[0]++;    }    return 0;}

高精度乘高精度

for(i = 0; i < ka; i++)    for(j = 0; j < kb; j++)    {      c[i + j] = c[i + j] + a[i] * b[j];      c[i + j +1] = c[i + j +1] + c[i + j]/10;      c[i + j] = c[i + j] % 10;    }  if(!c[k])  k--;

模板题链接：

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 2010using namespace std;string s1,s2;int a[MAXN+1],b[MAXN+1],c[MAXN+1];int main(){    cin>>s1>>s2;    a[0]=s1.length();    b[0]=s2.length();    int k=a[0]+b[0]+1;    for(int i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';    for(int i=1;i<=b[0];i++) b[i]=s2[b[0]-i]-'0';    if(a[a[0]]==0||b[b[0]]==0)     {        printf("0");        return 0;    }    for(int i=1;i<=a[0];i++)    {        for(int j=1;j<=b[0];j++)        {            c[i+j]=a[i]*b[j]+c[i+j];            c[i+j+1]=c[i+j+1]+c[i+j]/10;            c[i+j]=c[i+j]%10;                   }    }   //  printf("c[k]=%d",c[k-1]);    if(!c[k]) k--;    for(int i=k;i>1;i--)    {        printf("%d",c[i]);    }}

高精度除单精度

ll d=0;    for(int i= a[0];i>0;i--)    {        d=d *10 +a[i];        c[i]=d/b;        d=d%b;          }       while(c[a[0]]==0&&a[0]>1)  a[0]--;

模板题链接：

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 2010#define ll long longusing namespace std;string s1;ll b;int a[MAXN+1],c[MAXN+1];int main(){    cin>>s1>>b;    a[0]=s1.length();    for(int i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';    ll d=0;    for(int i= a[0];i>0;i--)    {        d=d *10 +a[i];        c[i]=d/b;        d=d%b;          }       while(c[a[0]]==0&&a[0]>1)  a[0]--;     for(int i=a[0];i>0;i--)    {        printf("%d",c[i]);    }}