C&C++   发布时间:2022-04-13  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了C语言程序设计100例之(68):大整数乘法大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

例68   大整数乘法

问题描述

求两个不超过200位的非负整数的积。

输入

有两行,每行是一个不超过200位的非负整数,没有多余的前导0。

输出

一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。

输入样例

12345678900

98765432100

输出样例

1219326311126352690000

        (1)编程思路。

        将大整数用字符串保存,编写函数void mul(char *a,char *b,char *c)实现大整数c=a*b。

        在函数中用int x[201]和int y[201]分别存放两个乘数,用int z[401]来存放积。计算的中间结果也都存在数组z中。数组z长度取401 是因为两个200 位的数相乘,积最多会有400 位。x[0], y[0], z[0]都表示个位。

         计算的过程基本上和小学生列竖式做乘法相同。为编程方便,不急于处理进位,而将进位问题留待最后统一处理。

         在乘法过程中,数组x的第i 位和y的第j 位相乘所得的数,一定是要累加到z的第i+j 位上。这里下标i, j 都是从右往左,从0 开始数。

(2)源程序。

#include <stdio.h>

#include <string.h>

void mul(char *a,char *b,char *c)

{

    int len1=strlen(a),len2=strlen(b);

    int x[201],y[201],z[401];

    int len=len1+len2;

    memset(x,0,sizeof(x));

    memset(y,0,sizeof(y));

    memset(z,0,sizeof(z));

    int i,j;

    for (i=len1-1;i>=0;i--)

        x[len1-1-i]=a[i]-'0';

    for (i=len2-1;i>=0;i--)

        y[len2-1-i]=b[i]-'0';

    for (i=0;i<len1;i++)

    {

        for (j=0;j<len2;j++)

        {

           z[i+j]+=x[i]*y[j];

        }

    }

    for (i=0;i<len;i++)

    {

        if (z[i]>=10)

        {

           z[i+1]+=z[i]/10;

           z[i]=z[i]%10;

        }

    }

    while (len>0 && z[len-1]==0) // 去前置0

        len--;

    if (len==0)  // a*b=0时特判

    {

        c[0]='0';

        c[1]='\0';

        return ;

    }

    for (i=0;i<len;i++)

        c[i]=z[len-1-i]+'0';

    c[len]='\0';

}

int main()

{

    char s1[201],s2[201],ans[401];

    scanf("%s%s",s1,s2);

    mul(s1,s2,ans);

    printf("%s\n",ans);

    return 0;

}

习题68

68-1  大整数除法

问题描述

求两个大的正整数相除的商。

输入

第1行是被除数,第2行是除数。每个数均不超过100位。

输出

一行,相应的商的整数部分

输入样例

2376

24

输出样例

99

         (1)编程思路。

        将大整数用字符串保存,编写函数void div(char *a,char *b,char *q)实现q=a/b。

        实现大整数除法的基本的思想是反复做减法,从被除数里最多能减去多少个除数,商就是多少。但是不能一个一个地减除数,这样既慢又不好处理。

        实际处理方法应该这样,将除数扩大10倍、100倍、…或10k倍,使得除数和被除数等长,之后再进行减法操作,依次减除数的10k倍、…、除数的100倍、除数的10倍、除数本身。每次记下够减的次数,所得结果就是商。

        下面以231568除以328为例进行说明。

        先将除数328扩大1000倍,即后面加上3个0,使得除数328000与被除数231568等长,231568减去328000,不够减,因此记下减的次数为0;之后,去掉除数后面的1个0,得到32800(即除数扩大100倍),231568减去32800,够减7次,余下 1968,同样记下减的次数为7;再去掉除数后面的1个0,得到3280(即除数扩大10倍),1968减3280,不够减,同样记下减的次数为0;再去掉除数后面的1个0,此时就是除数本身328,1968减328,够减6次,余下0,同样记下减的次数为6,结束运算。依次记下的减的次数为0706,去掉前导的0,商就是706。

        (2)源程序。

#include <stdio.h>

#include <string.h>

void sub(char *a,char *b,char *c)

{

    int len1=strlen(a),len2=strlen(b);

    int x[111],y[111],z[111];

    int len=len1;

    memset(x,0,sizeof(x));

    memset(y,0,sizeof(y));

    memset(z,0,sizeof(z));

    int i,j;

    for (i=len1-1,j=0;i>=0;i--,j++)

        x[j]=a[i]-'0';

    for (i=len2-1,j=0;i>=0;i--,j++)

        y[j]=b[i]-'0';

    int cf=0;

    for (i=0;i<len;i++)

    {

              z[i]=x[i]-y[i]+cf;

              if (z[i]<0)

              {

                     z[i]+=10;

                     cf=-1;

              }

        else

                     cf=0;

       }

    while (len>0 && z[len-1]==0) // 去前置0

        len--;

    if (len==0)  // a-b=0时特判

    {

        c[0]='0';

        c[1]='\0';

        return ;

    }

    for (i=0;i<len;i++)

        c[i]=z[len-1-i]+'0';

    c[len]='\0';

}

int bigger(char *a,char *b)

{

    if (strlen(a)>strlen(b)) return 1;

    if (strlen(a)<strlen(b)) return 0;

    if (strcmp(a,b)>=0) return 1;

    else return 0;

}

void div(char *a,char *b,char *q)

{

    if (bigger(a,b)==0)  // 被除数a小于除数b,商为0

    {

        q[0]='0';

        q[1]='\0';

        return ;

    }

    int len1=strlen(a);

    int len2=strlen(b);

    int i;

    for (i=len2;i<len1;i++)  // 将b的末尾添加0到与a等长

        b[i]='0';

    b[i]='\0';

    for (i=0;i<=len1-len2;i++)

    {

        int times=0;

        while (bigger(a,b))

        {

            times++;

            sub(a,b,a);

        }

        q[i]=times+'0';

        b[strlen(b)-1]='\0';

    }

    q[i]='\0';

    for (i=0;q[i]=='0';i++);

    strcpy(q,&q[i]);

}

int main()

{

    char a[115],b[115],q[115];

    scanf("%s", a);

    scanf("%s", b);

    div(a,b,q);

    printf("%s\n",q);

    return 0;

}

68-2  阶乘之和

问题描述

用高精度计算出 S = 1!+2!+3!+⋯+n!(n≤50)。

其中“!”表示阶乘,例如:5! = 5×4×3×2×1。

输入格式

一个正整数n。

输出格式

一个正整数 S,表示计算结果。

输入样例

3

输出样例

9

         (1)编程思路。

        编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数,得到乘积为大整数c。

        编写函数void bigNumAdd(char a[],char b[],char c[])实现大整数c=a+b。

        (2)源程序。

#include <stdio.h>

#include <string.h>

#define MAX_LEN 201

void bigNumAdd(char a[],char b[],char c[])

{

    int len1=strlen(a),len2=strlen(b);

    int x[MAX_LEN],y[MAX_LEN],z[MAX_LEN];

    int len=len1>len2?len1:len2;

    memset(x,0,sizeof(x));

    memset(y,0,sizeof(y));

    memset(z,0,sizeof(z));

    int i;

    for (i=len1-1;i>=0;i--)

        x[len1-1-i]=a[i]-'0';

    for (i=len2-1;i>=0;i--)

        y[len2-1-i]=b[i]-'0';

    int cf=0;

    for (i=0;i<len;i++)

    {

        z[i]=(x[i]+y[i]+cf)%10;

        cf=(x[i]+y[i]+cf)/10;

    }

    z[len++]=cf;

    while (len>0 && z[len-1]==0) // 去前置0

        len--;

    if (len==0)  // a+b=0时特判

    {

        c[0]='0';

        c[1]='\0';

        return ;

    }

    for (i=0;i<len;i++)

        c[i]=z[len-1-i]+'0';

    c[len]='\0';

}

void bigNumMul(char a[],int b,char c[])  // C=a*b

{

      int num[MAX_LEN]={0},result[MAX_LEN+10]={0};

      // 将a中存储的字符串形式的整数转换到num中去,

      // num[0]对应于个位、num[1]对应于十位、……

      int len1 = strlen(a);

      int i,j;

      for (i=len1-1,j=0;i>=0; i--)

         num[j++] = a[i] - '0';

      int len2 =0;

      int t=b;

      do {

           len2++;

           t=t/10;

       } while (t!=0);

       for (i=0;i < len1; i++)

            result[i] = num[i]*b;

       //   统一处理进位问题

       int len=len1+len2;

       for (i = 0; i < len; i++)

       {

           if (result[i] >= 10)

           {

                result[i+1] += result[i] / 10;

                result[i] %= 10;

           }

       }

    while (len>0 && result[len-1]==0) // 去前置0

        len--;

    if (len==0)  // a*b=0时特判

    {

        c[0]='0';

        c[1]='\0';

        return ;

    }

    for (i=0;i<len;i++)

        c[i]=result[len-1-i]+'0';

    c[len]='\0';

}

int main()

{

        char a[MAX_LEN],s[MAX_LEN];

     int n,i;

     scanf("%d",&n);

     a[0]='1', a[1]='\0';

        s[0]='1'; s[1]='\0';

     for (i=2;i<=n;i++)

        {

        bigNumMul(a,i,a);

        bigNumAdd(s,a,s);

        }

     printf("%s\n",s);

     return 0;

}

68-3  Hillwer编码

问题描述

Hillwer编码的转换规则如下:对于每一条原码S,保证仅由26个大写字母组成。将每个字母后移R位,得到中转码S1(当S=‘XYZ’,R=2时,S1=‘ZAB’。即变成当前字母后R个字母,超过‘Z’则从‘A’开始)。接着,将中转码进行“符转数”操作,将S1每一位的ACS码(即ASCLL码)相乘,得到数串Q。转换后的编码即为Q。

输入

第1行,读入n,R。第2~n+1行,每行一条编码S。

输出

共n*2行,奇数行,每行一条中转码S1; 偶数行,每行一条转换后的编码Q。

输入样例

2 6

HELLOWORLD

LETUSGO

输出样例

NKRRUCUXRJ

10167740864629920000

RKZAYMU

20957073637500

         (1)编程思路1。

        将S1中每一个字符的ASCLL码相乘得到的数串Q超出了长整数的表示范围,因此需要进行高精度乘法运算。

        编写函数void bigNumMul(char a[],int b,char c[])实现一个大整数a乘以一个int型整数,得到乘积为大整数c。

       (2)源程序1。

#include <stdio.h>

#include <string.h>

void bigNumMul(char a[],int b,char c[])  // C=a*b

{

      int num[1300]={0},result[1300+10]={0};

      // 将a中存储的字符串形式的整数转换到num中去,

      // num[0]对应于个位、num[1]对应于十位、……

      int len1 = strlen(a);

      int i,j;

      for (i=len1-1,j=0;i>=0; i--)

         num[j++] = a[i] - '0';

      int len2 =0;

      int t=b;

      do {

           len2++;

           t=t/10;

       } while (t!=0);

       for (i=0;i < len1; i++)

            result[i] = num[i]*b;

       //   统一处理进位问题

       int len=len1+len2;

       for (i = 0; i < len; i++)

       {

           if (result[i] >= 10)

           {

                result[i+1] += result[i] / 10;

                result[i] %= 10;

           }

       }

    while (len>0 && result[len-1]==0) // 去前置0

        len--;

    if (len==0)  // a*b=0时特判

    {

        c[0]='0';

        c[1]='\0';

        return ;

    }

    for (i=0;i<len;i++)

        c[i]=result[len-1-i]+'0';

    c[len]='\0';

}

int main()

{

       int n,r;

    scanf("%d%d",&n,&r);

    r=r%26;

    char s[600],q[1300];

    while(n--)

    {

       scanf("%s",s);

       q[0]='1';

       q[1]='\0';

       int i;

       for (i=0;s[i]!='\0';i++)

       {

           if (s[i]+r<='Z') s[i]=s[i]+r;

           else s[i]=s[i]+r-'Z'+'A'-1;

           bigNumMul(q,(int)s[i],q);

       }

       printf("%s\n",s);

       printf("%s\n",q);

    }

    return 0;

}

        (3)编程思路2。

        在上面的源程序1中,实现大整数乘法时,保存大整数的数组num中,每个数组元素保存1位数字,这样既浪费存储空间,又耗费计算时间。实际上,一个数组元素中可以保存大整数的6位数字,因为它与一个ASCII码(最多为3位整数)相乘,不会超过int型整数的表数范围。下面的源程序2就是按这个想法编写的。

      (4)源程序2。

#include <stdio.h>

#include <string.h>

#define MOD 1000000

void work(char s[])

{

    int q[205];

    memset(q,0,sizeof(q));

    int len=1;

    q[1]=1;

    int i,j;

    for (i=0;s[i]!='\0';i++)

    {

        int t=(char)s[i];

        for (j=1;j<=len;j++)

           q[j]=q[j]*t;

        int cf;

        for (j=1;j<=len;j++)

        {

           cf=q[j]/MOD;

           q[j]=q[j]%MOD;

           q[j+1]+=cf;

        }

        if (q[len+1]!=0)

        {

            len++;

        }

    }

    printf("%d",q[len]);

    for (i=len-1;i>=1;i--)

       printf("%06d",q[i]);

    printf("\n");

}

int main()

{

    int n,r;

    scanf("%d%d",&n,&r);

    while (n--)

    {

        char s[605];

        scanf("%s",s);

        int i;

        for (i=0;s[i]!='\0';i++)

        {

            s[i]=(s[i]-'A'+r)%26+'A';

        }

        printf("%s\n",s);

        work(s);

    }

    return 0;

}

大佬总结

以上是大佬教程为你收集整理的C语言程序设计100例之(68):大整数乘法全部内容,希望文章能够帮你解决C语言程序设计100例之(68):大整数乘法所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: