首页 > 代码库 > 【算法:1】高精度除法

【算法:1】高精度除法

高精度除法,我用高精度减法来模拟

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<string>using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch==-) f=-1;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-0;    return x*f;}const int maxn=10000;int a[maxn],b[maxn],c[maxn];void in(int a[]) //这个函数用来输入,输入时将字符串转化为int数组,角标为0的为长度。并倒序存储。 {    string s;    cin>>s;    a[0]=s.length();    for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-0;    return ;}void print(int a[]) // 输出{    if( !a[0] ) puts("0");    else     {        for(int i=a[0];i>0;i--) printf("%d",a[i]);        puts("");    }    return ;}int compare( int a[], int b[]) // 比较函数,如果a<b,返回-1,如果a>b,返回1,如果a=b,返回0 {    if( a[0] > b[0] ) return 1;    if( a[0] < b[0] ) return -1;    for(int i=a[0];i>0;i--)    {        if(a[i] > b[i]) return 1;        else if( a[i] < b[i] ) return -1;     }    return 0;}void sub(int a[], int b[])//高精度减法 {    int flag=compare(a,b);    if( !flag) {a[0]=0;return ;}    if( flag == 1 )     {        for(int i=1;i<=a[0];i++)        {            if( a[i] < b[i] )             {                a[i+1]--;                a[i]+=10;            }            a[i]-=b[i];        }        while( a[0] > 0 && !a[a[0]] ) a[0]--;    }    return ;}void numcpy(int p[], int q[],int det) //复制p数组到q数组从det开始的地方 {    for(int i=1;i<=p[0];i++) q[i+det-1]=p[i];    q[0]=p[0]+det-1;    return ;}void div(int a[], int b[], int c[]){    int tmp[maxn];    c[0]=a[0]-b[0]+1;    for(int i=c[0];i>0;i--)    {        memset(tmp,0,sizeof(tmp));        numcpy(b,tmp,i);        while( compare(a,tmp) >= 0) {c[i]++;sub(a,tmp);} //用减法模拟除法     }    while(c[0] > 0 && !c[c[0]]) c[0]--;    return ;}int main(){    in(a),in(b),div(a,b,c),print(c),print(a);}

 

【算法:1】高精度除法