杭电ACM 1002:A+B Problem II
刷题第三篇，这一题看似也比较简单，但是一做就错，花费了很大力气才把他搞定。切记一定要亲自用笔画图算出，这样收获才会更大。
原题回顾
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 = 3Case 2:
112233445566778899 + 998877665544332211 = >1111111111111111110
可能很所人看到这个题目就匆忙下手，得出自己认为所谓的正确答案。我自己也是一开始就提交下述代码，最后“Wrong Error“才知道自己想的太过于简单了。
#include <stdio.h>
int main()
{
int t;
int a,b,sum=0;
scanf("%d",&t);
if(t<1||t>20) return -1;
for(int i=1;i<=t;i++)
{
scanf("%d%d",&a,&b);
sum=a+b;
printf("Case : %d\n",i);
printf("%d + %d = %d",a,b,sum);
sum=0;
}
return 0;
}其实写完上述代码时候就觉得肯定是错的，因为好几个地方的条件我都没有考虑进去。首先是这一个条件**” 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.“** 所以直接定义为整型时行不通的，这里也提到的位数，那么就想到可以用数组来进行计算。
解题思路：
- 定义两个字符数组来保存按字符输入的两个加数，在定义两个整形数组来保存每位转换后的a和b,数组的大小1000左右。
- 接下来一个难点就是如何将字符数组的每一位存到整形数组中去，再将不同位数的加数变为位数相同的加数，即最大数组下标多开了一位，另一个数组位数也随之要改成一样。因为这样的话在后面相加代码比较好算。
- 再接下来就是数组求和，有了第二步的位数对齐，在这一步直接各位相加，有进位的话就在向前进位。
- 最后就是格式控制好输出。
下面是我写的代码，并且Accept：
#include<iostream>
#include<string>
using namespace std;
int main(void){
char a[1000],b[1000];
int a_int[1001],b_int[1001];
int t,a_len,b_len,max_len;
//t判断case次数
cin>>t;
for(int i=1;i<=t;i++){
cin>>a>>b;
//计算两个数组实际长度
a_len=strlen(a);
b_len=strlen(b);
int tmp=0;
//将字符数组值反向存入整形数组,输入的数字的个位数在a_int[0]
for(int j=a_len-1;j>=0;j--)
{
a_int[tmp++]=a[j]-'0';
}
tmp=0;
for(int k=b_len-1;k>=0;k--){
b_int[tmp++]=b[k]-'0';
}
///将两数组用0填充使其位数相等,他们填充后的位数是最大位数加1，而不是只到最大位数，这是为了后面计算方便
if(a_len>b_len)
{
for(int j=b_len;j<=a_len;j++){
b_int[j]=0;
}
a_int[a_len]=0;
}else if(a_len<b_len){
for(int j=a_len;j<=b_len;j++)
{
a_int[j]=0;
}
b_int[b_len]=0;
}else{//当两个位数一样时，都留出1位给进位
a_int[a_len]=0;
b_int[b_len]=0;
}
//求和，最后保存到a_int里面
max_len=(a_len>=b_len)?a_len:b_len;
for(int j=0;j<=max_len;j++){
a_int[j]+=b_int[j];
if(a_int[j]>=10)
{
a_int[j]-=10;
a_int[j+1]+=1;
}
}
cout<<"Case "<<i<<":"<<endl;
cout<<a<<" "<<"+"<<" "<<b<<" "<<"="<<" ";
//判断最高位是否有进位，有就输出
if(a_int[max_len]==0){
for(int j=max_len-1;j>=0;j--)
cout<<a_int[j];
}else{
for(int j=max_len;j>=0;j--)
cout<<a_int[j];
}
if(i!=t)
cout<<endl<<endl;
else
cout<<endl;
}
}最后格式输入不看清楚的话也很容易会弄错。
注意
最后的格式输出是这样的，当最外层循环结束时结果后面只有一个回车（换行而已）。当外层循环还没结束即两个case之间是空一行的（这需要两个回车）。在我的if语句就能看出来。当时自己看了半天没有看出来，急死我了。
这一道题目确实比较有挑战力，不做不知道，一做下一跳。一定要自己动手敲代码，这样才有成就感。