HDU 1002 A + B Problem II

A + B Problem II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 310717 Accepted Submission(s): 60078

Problem Description

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

Sample Input

2 1 2 112233445566778899 998877665544332211

Sample Output

Case 1:

1 + 2 = 3

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

Recommend

We have carefully selected several similar problems for you: 1004 1003 1008 1005 1089

解题心得：

　　这是个大数问题，题意要求计算不超过1000位的两个数字相加，所以必须要用字符串存储两个数字。

　　我刚开始选择的是让他们从最低位开始相加，但是两个字符串需要考虑长度问题，写完后有发现很多问题。

　　忽略了进位问题，可能不止进一位，当99999+1时就需要进好几位。结果一遍一遍的改就是不对，下面的代码是错误的。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    int n;
    char a[1005],b[1005],ab[1005];
    int c_a,c_b;
    int i1=0,i2=0,ii;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s %s",a,b);
        printf("Case %d:\n",i+1);
        c_a=strlen(a);
        c_b=strlen(b);
        if(c_a<c_b){
            for(int j=c_a;j>=0;j--){
                a[j+c_b-c_a+1]=a[j];
            }
            for(int j=c_b-1;j>=0;j--){
                b[j+1]=b[j];
            }
            memset(a,'0',(c_b-c_a+1)*sizeof(char));
            memset(ab,'0',c_b*sizeof(char));
            for(int j=c_a+1;j>=0;j--){
                ii=(int)(a[j]-48)+(int)(b[j]-48)+i2;
                i1=ii/10;
                i2=ii%10;
                ab[j]=(char)(i2+48);
                i2=i1;
            }
            ab[c_b+1]='\0';
            if(i2!=0){
                ab[0]=(char)(i2+48);
            }
            if(ab[0]=='0'){
                printf("%s + ",&a[c_b-c_a+1]);
                printf("%s = ",b+1);
                printf("%s\n",ab+1);
            }else{
                printf("%s + ",&a[c_b-c_a+1]);
                printf("%s = ",b+1);
                printf("%s\n",ab);
            }

            i2=i1=0;
        }
        if(c_a==c_b){
            for(int j=c_a-1;j>=0;j--){
                a[j+1]=a[j];
            }
            for(int j=c_a-1;j>=0;j--){
                b[j+1]=b[j];
            }
            memset(a,'0',1*sizeof(char));
            memset(b,'0',1*sizeof(char));
            memset(ab,'0',1*sizeof(char));
            for(int j=c_a;j>=0;j--){
                ii=(int)(a[j]-48)+(int)(b[j]-48)+i2;
                i1=ii/10;
                i2=ii%10;
                ab[j]=(char)(i2+48);
                i2=i1;
            }

            ab[c_a+1]='\0';
            if(ab[0]!='0'){
                printf("%s + ",a+1);
                printf("%s = ",b+1);
                printf("%s\n",ab);
            }
            else{
                printf("%s + ",a+1);
                printf("%s = ",a+1);
                printf("%s\n",&ab[1]);
            }

            i1=i2=0;
        }
        if(c_a>c_b){
            for(int j=c_b;j>=0;j--){
                b[j+c_a-c_b]=b[j];
            }
            memset(b,'0',(c_a-c_b)*sizeof(char));
            for(int j=c_b;j>=0;j--){
                ii=(int)(a[j]-48)+(int)(b[j]-48)+i2;
                i1=ii/10;
                i2=ii%10;
                ab[j]=(char)(i2+48);
                i2=i1;
            }
            i1=i2=0;
            ab[c_a]='\0';
            printf("%s + ",&a[0]);
            printf("%s = ",&b[c_a-c_b]);
            printf("%s\n",&ab[0]);
        }
    }
    return 0;
}

View Code

　　然后上网百度之后发现反着计算更简单，把低位存储在啊a[0]的位置，高位往后存，这样不用考虑长度问题，进位问题也好解决。

　　下面是代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    int n;
    int i1=0;
    char a[1000],b[1000];
    int la,lb;
    int c[1000]={0};
    scanf("%d",&n);
    for(int t=1;t<=n;t++){
        scanf("%s %s",&a,&b);
        la=strlen(a)-1;
        lb=strlen(b)-1;
        for(int i=la;i>=0;i--){
            c[i1++]=(a[i]-'0');
        }
        i1=0;
        for(int i=lb;i>=0;i--){
            c[i1++]+=(b[i]-'0');
            if(c[i1-1]>=10){
                c[i1-1]-=10;
                c[i1]++;
            }
        }
        while(c[i1]!=0){
            if(c[i1]>=10){
                c[i1]-=10;
                c[i1+1]++;
            }
            i1++;
        }
        printf("Case %d:\n",t);
        printf("%s + %s = ",a,b);
        i1=la>lb?la:lb;
        if(c[i1+1]!=0){
            printf("%d",c[i1+1]);
        }
        for(int j=i1;j>=0;j--){
            printf("%d",c[j]);
        }
        i1=0;
        if(t!=n){
           printf("\n\n");
        }else{
            printf("\n");
        }
        memset(c,0,1000*sizeof(int));
    }
    return 0;
}

View Code

　　这个题也要注意格式问题！！

又重新做了这个题，下面是代码：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[1001]={'0'};
char b[1001]={'0'};
int c[1001]={0};


int main()
{
    int g,s;
    int n;
    cin>>n;
    for(int cou=0;cou<n;cou++){
        scanf("%s",&a[1]);
        scanf("%s",&b[1]);
        int la=strlen(a);
        int lb=strlen(b);
        if(la<lb){
            for(int i=la-1,j=lb-1,k=lb-1;i>0&&j>0;i--,j--,k--){
                c[k]+=(int)(a[i]-'0')+(int)(b[j]-'0');
                if(c[k]>=10){
                    g=c[k]%10;
                    s=c[k]/10;
                    c[k]=g;
                    c[k-1]+=s;
                }
            }
            for(int i=lb-la;i>=0;i--){
                c[i]+=(int)(b[i]-'0');
                if(c[i]>=10){
                    g=c[i]%10;
                    s=c[i]/10;
                    c[i]=g;
                    c[i-1]+=s;
                }
            }
        }
        if(la>lb){
            for(int i=lb-1,j=la-1,k=la-1;i>0&&j>0;i--,j--,k--){
                c[k]+=(int)(b[i]-'0')+(int)(a[j]-'0');
                if(c[k]>=10){
                    g=c[k]%10;
                    s=c[k]/10;
                    c[k]=g;
                    c[k-1]+=s;
                }
            }
            for(int i=la-lb;i>=0;i--){
                c[i]+=(int)(a[i]-'0');
                if(c[i]>=10){
                    g=c[i]%10;
                    s=c[i]/10;
                    c[i]=g;
                    c[i-1]+=s;
                }
            }
        }
        if(la==lb){
            for(int i=lb-1,j=la-1;i>0&&j>0;i--,j--){
                c[i]+=(int)(b[i]-'0')+(int)(a[j]-'0');
                if(c[i]>=10){
                    g=c[i]%10;
                    s=c[i]/10;
                    c[i]=g;
                    c[i-1]+=s;
                }
            }
        }
        int l= la>=lb ? la:lb;
        printf("Case %d:\n",cou+1);
        printf("%s + ",&a[1]);
        printf("%s = ",&b[1]);
        if(c[0]!=0){
            for(int i=0;i<l;i++){
                printf("%d",c[i]);
            }
        }else{
            for(int i=1;i<l;i++){
                printf("%d",c[i]);
            }
        }
        memset(c,0,1001*sizeof(int));
        //if(cou!=n-1){
            printf("\n");
        //}

    }
    return 0;
}