C/C++教程

C语言程序设计100例之(67):大整数加法

本文主要是介绍C语言程序设计100例之(67):大整数加法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

例67  大整数加法

问题描述

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

输入

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

输出

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

输入样例

22222222222222222222

33333333333333333333

输出样例

55555555555555555555

        (1)编程思路。

        可以用一个字符串来保存200位整数。

        编写函数void add(char *a,char *b,char *c)实现大整数c=a+b。

        在函数中可以用数组unsigned x[201]来保存一个200 位的整数a,让x[0]存放个位数,x[1]存放十位数,x[2]存放百位数……。

        实现两个大整数相加的方法很简单,就是模拟小学生列竖式做加法,从个位开始逐位相加,超过或达到10 则进位。

(2)源程序。

#include <stdio.h>

#include <string.h>

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

{

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

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

    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';

}

int main()

{

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

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

    add(s1,s2,ans);

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

    return 0;

}

习题67

67-1  二进制加法

问题描述

给出两个二进制数a和b的01串,按二进制加法计算a+b并输出。

输入

第1行为一个整数T,表示测试用例的组数,之后T行,每行包括两个01串,每个串长不超过80位。

输出

对于每组测试用例,输出两个01串相加的结果(最简形式)。

输入样例

3

1001101 10010

1001001 11001

1000111 1010110

输出样例

1 1011111

2 1100010

3 10011101

        (1)编程思路。

        二进制数高精度加法,注意前置0的处理。

       (2)源程序。

#include <stdio.h>

#include <string.h>

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

{

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

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

    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)%2;

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

    }

    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';

}

int main()

{

    char s1[91],s2[91],ans[91];

    int n,i;

    scanf("%d",&n);

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

    {

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

        binAdd(s1,s2,ans);

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

    }

    return 0;

}

67-2  大整数减法

问题描述

求两个大的正整数相减的差。

输入

共2行,第1行是被减数a,第2行是减数b(a > b)。每个大整数不超过200位,不会有多余的前导零。

输出

一行,即所求的差。

输入样例

9999999999999999999999999999999999999

9999999999999

输出样例

9999999999999999999999990000000000000

         (1)编程思路。

        可以用一个字符串来保存200位整数。

        编写函数voidsub(char *a,char *b,char *c)实现大整数c=a-b。

        在函数中可以用数组unsigned x[201]来保存一个200 位的整数a,让x[0]存放个位数,x[1]存放十位数,x[2]存放百位数……。

        实现两个大整数相减的方法很简单,就是模拟小学生列竖式做减法,从个位开始逐位相减,小于0则向前借位补10。

       (2)源程序。

#include <stdio.h>

#include <string.h>

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

{

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

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

    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 main()

{

    char a[210],b[210],c[210];

    scanf("%s", a);

    scanf("%s", b);

    sub(a,b,c);

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

    return 0;

}

67-3  求和

问题描述

已知两个整数a和b,求a+b的值

输入

第一行包含一个整数T,即测试用例的数量。

以下T行,每行分别包含2个整数A、B(-10^50000<A、B<32768)。

输出

输出应该包含T行,每个行都有一个整数,代表相应的和。

输入样例

2

1 2

-1 +2

输出样例

3

1

        (1)编程思路。

        由于a和b可能小于0,因此a+b分为4种情况:

        1)a>=0,b>=0,则进行a+b;

        2)a<0,b<0,则进行(-a)+(-b);

        3)a>=0,b<0,则进行a-(-b);此时还需对a和(-b)进行大小比较,按比较情况执行a-(-b)或(-b)-a;

        4)3)a<0,b>=0,则进行b-(-a);此时还需对-a和b进行大小比较,按比较情况执行b-(-a)或(-a)-b。

       (2)源程序。

#include <stdio.h>

#include <string.h>

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

{

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

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

    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 sub(char *a,char *b,char *c)

{

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

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

    int len=len1;

    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;

              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;

}

int main()

{

    int t;

       scanf("%d",&t);

       while(t--)

      {

              char a[51000],b[51000],ans[51000];

              scanf("%s%s",a,b);

              if (a[0]=='+') strcpy(a,&a[1]);

              if (b[0]=='+') strcpy(b,&b[1]);

              int sign;

              if (a[0]!='-' && b[0]!='-')       // a+b

              {

                   add(a,b,ans);

                  sign=0;

              }

              else if (a[0]=='-' && b[0]=='-')  // -a-b=-(a+b)

              {

                     add(&a[1],&b[1],ans);

                     sign=1;

              }

              else if (a[0]!='-' && b[0]=='-')  // a-b

              {

                     if (bigger(a,&b[1]))

                     {

                sub(a,&b[1],ans);

                sign=0;

     }

                     else                 // b>a,a-b=-(b-a)

                     {

                            sub(&b[1],a,ans);

                            sign=1;

                     }

              }

              else                    // b-a

             {

                     if (bigger(b,&a[1])) // b>a

                     {

                            sub(b,&a[1],ans);

                            sign=0;

                     }

                     else                // b<a,b-a=-(a-b)

                    {

                          sub(&a[1],b,ans);

                          sign=1;

                    }

              }

              if (sign==1 && ans[0]!='0') printf("-");

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

       }

       return 0;

}

这篇关于C语言程序设计100例之(67):大整数加法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!