May 12

高精度整数除法   不指定

felix021 @ 2007-5-12 09:38 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(7609) | Via 本站原创 | |
高精度整数除法 
1.求A÷B的精确值   
   
    由于A和B都是计算机允许的显示精度,故A、B均可使用数值变量来接收与存储。A÷B的精确值有两种情况:   
   
    ①、A能被B整除,没有余数。   
    ②、A不能被B整除,对余数进行处理。首先,我们知道,在做除法运算时,有一个不变的量和三个变化的量,不变的量是除数,三个变化的量分别是:被除数、商和余数。做除法运算时,每次都是用被除数减去商与除数的积,如果所得余数不为零,则将其扩大10倍再次作为被除数,继续试除,直至余数为零或达到要求的精确度为止。最后,必须对精确度的后一位求商,然后判断其值而四舍五入得出最后的结果。   
   
  2.求多精度A÷单精度B的商和余数。   
   
    ①、数据的接收和存储   
   
    采用字符串输入的方式,设参与运算的两个数分别为A和B,利用字符串函数把字符串转化为数值,将A中的每一位数字分别存储在A数组中,最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据,而后通过ORD(x)-48的方式转化成数值。)。B则可以用一般的整数变量来接收和存储。   
   
    ②、算法   
   
    首先,我们知道,在做除法运算时,有一个不变的量和三个变化的量,不变的量是除数,三个变化的量分别是:被除数、商和余数。做除法运算时,每次都是用被除数减去商与除数的积,如果所得余数不为零,则将其扩大10倍再次作为被除数,继续试除,直至余数为零或达到要求的精确度为止。   
   
  3.求多精度A÷多精度B的商和余数。   
   
    ①、数据的接收和存储   
   
    采用字符串输入的方式,设参与运算的两个数分别为A和B,利用字符串函数把字符串转化为数值,将A、B中的每一位数字分别存储在A和B数组中,最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据,而后通过ORD(x)-48的方式转化成数值。)。   
   
    ②、算法   
   
    可以用减法代替除法运算:不断比较A[1..n]与B[1..n]的大小,如果A[1..n]>=B[1..n]则商C[1..n]+1→C[1..n],然后就是一个减法过程:A[1..n]-B[1..n]→A[1..n]。由于简单的减法速度太慢,故必须进行优化。设置一个位置值J,当A[1..n]>B[1..n]时。B[1..n]左移→B[0..n],j:=j+1,即令B[1..n]增大10倍。这样就减少了减法的次数。当j>0且A[1..n]

高精度整数除法是高精度加减乘的综合!   

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int cchkdig(char *r)
{
    int i=0;
    while(r[i]!='\0')
    {
        if(isdigit(r[i++])==0)
            return (0);
    }
    return (1);
}

//去掉整数串表示前面多余的零,最后结果为空串时置为"0"
void cdel0(char *r)
{
    unsigned int lr;
    int i=0, j;
    lr=strlen(r);
    while(r[i]=='0')
        ++i;
    if(i>0)
    {
        for(j=0; j<lr-i; ++j)
            r[j]=r[j+i];
        for(j=lr-i; j<lr; ++j)
        {
            r[j]='\0';
        }

    }

    if(r[0]=='\0')
    {
        r[0]='0';
    }
}

int scmp(char *r, char *u)
{
    unsigned int lr, lu;
    cdel0(r);
    cdel0(u);

    lr=strlen(r);
    lu=strlen(u);

    if(lr>lu)
    {
        return 1;
    }
    else if (lr<lu)
    {

        return -1;
    }
    return (strcmp(r, u));

}//end scmp()

//两个串表示数的减法
char *ssub(char *r, char *u)
{
    unsigned int i,lr, lu, lp,c=0;
    char h,hc;
    char *p;
    if(scmp(r, u)<0)
        return NULL;
    lr=strlen(r);
    lu=strlen(u);
    p=(char *)malloc((unsigned int)(lr+1)*sizeof(char));
    for(i=0; i<lu; ++i)
    {
        h=r[lr-i-1]-u[lu-i-1]-c;
        if(h<0)
        {
            c=1;
            h=h+10;
        }
        else
            c=0;
        p[i]=h+'0';
        hc=h+'0';
    }
    for (i=lu; i<lr; ++i)
    {
        h=r[lr-i-1]-'0'-c;
        if(h<0)
        {
            c=1;
            h=h+10;
        }
        else
            c=0;
        p[i]='0'+h;
        hc='0'+h;
    }
    p[i]='\0';
    lp=i-1;

    while(p[lp]=='0'&&lp!=0)
    {
        p[lp]='\0';
        lp--;
    }


    for(i=0; i<(lp+1)/2; ++i)
    {
        hc=p[i];
        p[i]=p[lp-i];
        p[lp-i]=hc;
    }
    return (p);
}//end ssub()

//两个串表示数的加法
char *sadd(char *r, char *u)
{
    unsigned int lr, lu, lp;
    int i, h, c=0;
    char hc, *p;
    lr=strlen(r);
    lu=strlen(u);
    if(lu>lr)
    {
        p=r;
        r=u;
        u=p;
        h=lr;
        lr=lu;
        lu=h;
    }
    p=(char *)malloc((unsigned int)(lr+2)*sizeof(char));
    for(i=0; i<lu; ++i)
    {
        h=r[lr-i-1]-'0'+u[lu-i-1]-'0'+c;
        if(h>9)
        {
            c=1;
            h=h-10;
        }
        else
            c=0;
        p[i]=h+'0';
    }
    for(i=lu; i<lr; ++i)
    {
        h=r[lr-i-1]-'0'+c;
        if(h>9)
        {
            c=1;
            h=h-10;
        }
        else
            c=0;
        p[i]='0'+h;
    }
    if(c>0)
    {
        p[i]=c+'0';
        lp=i;
    }
    else
        lp=i-1;
    for(i=lp+1; i<lr+2; ++i)
        p[i]='\0';
    for(i=0; i<(lp+1)/2; ++i)
    {
        hc=p[i];
        p[i]=p[lp-i];
        p[lp-i]=hc;
    }
    return (p);
}//end sadd()

//两个串表示数的乘法
char *smut(char *r, char *u)
{
    unsigned int lr, lu, lp;
    int i, j, c, h;
    char *p;
    lr=strlen(r);
    lu=strlen(u);
    p=(char *)malloc((unsigned int)(lr+lu+1)*sizeof(char));
    for(i=0; i<lr+lu; ++i)
        p[i]='0';
    p[lr+lu]='\0';

    for(i=lr-1; i>=0; --i)
    {
        c=0;
        for(j=lu-1; j>=0; --j)
        {
            lp=i+j+1;
            h=(r[i]-'0')*(u[j]-'0')+p[lp]-'0'+c;
            c=h/10;
            h=h%10;
            p[lp]=h+'0';
        }
        if(c>0)p[i+j+1]=c+'0';
    }

    cdel0(p);
    return p;
}//end smut()

//两个串表示数的除法,结果精确到小数点后第n位
char *sdivf(char *u, char *v, int n)
{
    char *p, *f, *r,*q;
    unsigned int i, lu, lv, lr, iw, c, h;
    int kh, j;
    lu=strlen(u);
    lv=strlen(v);
    f=(char *)malloc((unsigned int)(lu+n+3)*sizeof(char));
    q=(char *)malloc(sizeof(char));
    for(i=0; i<lu+n+3; ++i)
        f[i]='\0';
    r=(char *)malloc((unsigned int)(lv+2)*sizeof(char));
    for(i=0; i<lv+2; ++i)
        r[i]='\0';
    for(iw=0; iw<lu+n+2; ++iw)
    {
        if(iw<lu)
        {
            cdel0(r);
            lr=strlen(r);
            r[lr]=u[iw];
            r[lr+1]='\0';
        }

        else if(iw>lu)
        {
            cdel0(r);
            q[0]='0';
            if(scmp(r, q)==0)
            {
                break;
            }
            lr=strlen(r);
            r[lr]='0';
            r[lr+1]='\0';
        }

        else
        {
            f[lu]='.';
            continue;
        }

        kh=0;
        while(scmp(r, v)>=0)
        {
            p=r;
            r=ssub(p, v);
            ++kh;
        }
        f[iw]=kh+'0';
    }
    if(iw==lu+n+2)
    {
        if(f[lu+n+1]>='5')
        {
            f[lu+n+1]='\0';
            c=1;
            for(j=lu+n; j>=0; --j)
            {
                if(c==0)
                {
                    break;
                }
                if(f[j]=='.')
                {
                    continue;
                }
                h=f[j]-'0'+c;
                if(h>9)
                {
                    h=h-10;
                    c=1;
                }
                else
                    c='\0';
                f[j]=h+'0';
            }
        }
        else
            f[lu+n+1]='\0';

    }
    free(r);
    free(p);
    q=NULL;
    free(q);
    cdel0(f);
    return(f);
}//end sdivf()

//两个串表示数的除法,结果分别用整商与余数表示
char *sdivkr(char *u, char *v, char **rout)
{
    char *f, *r;
    unsigned int i, lu, lv, lr, iw;
    int kh;
    lu=strlen(u);
    lv=strlen(v);

    f=(char *)malloc((unsigned int)(lu+1)*sizeof(char));
    for(i=0; i<lu+1; ++i) f[i]='\0';
    r=(char *)malloc((unsigned int)(lv+2)*sizeof(char));
    for(i=0; i<lv+2; ++i) r[i]='\0';

    for(iw=0; iw<lu; ++iw)
    {
        cdel0(r);
        lr=strlen(r);
        r[lr]=u[iw];
        r[lr+1]='\0';
        kh=0;
        while(scmp(r, v)>=0)
        {
            r=ssub(r, v);
            ++kh;
        }
        f[iw]=kh+'0';
    }
    cdel0(r);
    *rout=r;
    cdel0(f);
    return(f);

}//end *sdivkr()

//调用上述函数实现两任意长正整数任意指定精度的算术计算器程序
int main(int argc, char *argv[])
{
    char *p, *r;
    int n;
    if(argc!=4)
    {
        if(argc!=3)
            printf("\n>>\"order n1 op n2\" or n ! ");
        exit(0);
    }
    cdel0(argv[1]);
    if(cchkdig(argv[1])==0)
    {
        printf("Input data error, Input again!");
        exit(0);
    }
    cdel0(argv[3]);
    if(cchkdig(argv[3])==0)
    {
        printf("Input data error, Input again!");
        exit(0);
    }

    if(strcmp(argv[2], "+")==0)
    {
        printf("%s", p=sadd(argv[1], argv[3]));
        free(p);
    }

    else if(strcmp(argv[2], "-")==0)
    {
        printf("%s", p=ssub(argv[1], argv[3]));
        free(p);
    }

    else if(strcmp(argv[2], "*")==0)
    {
        printf("%s", p=smut(argv[1], argv[3]));
        free(p);
    }

    else if(argv[2][0]=='/' && strlen(argv[2])==1)
    {
        if(argv[3][0]=='0')
        {
            printf("error!devided by zero!!\n");
            exit(0);
        }
        p=sdivkr(argv[1], argv[3], &r);
        printf("k=%s r=%s", p, r);
        free(p);
        free(r);
    }

    else if(argv[2][0]=='/'&&strlen(argv[2])>1)
    {
        if(argv[3][0]=='0')
        {
            printf("error!devided by zero!!\n");
            exit(0);
        }

        argv[2][0]='\0';
        cdel0(argv[2]);
        if(cchkdig(argv[2])==0)
        {
            printf("Input data error, Input again!");
            exit (0);
        }
        n=atoi(argv[2]);
        printf("%s", p=sdivf(argv[1], argv[3], n));
        free(p);
    }
    return 0;
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
小流氓 Email Homepage
2014-10-18 20:18
博主,你可以修改一下你的代碼縮進嗎,,這樣看著很不清楚
felix021 回复于 2014-10-19 01:21
好的。这大概是很早以前从别人那里转载过来的,回想起来估计自己也没认真看过呢。。
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]