题目链接在此☞http://acm.hdu.edu.cn/showproblem.php?pid=1002
这题也比较简单,只需要开三个长度为1000的char数组来分别储存a、b、ans,再利用我们加法的算法,先向右对齐再相加。注意一下进位时的特殊情况就好了。
不过笔者的代码写好后提交上去,两次Presentation Error,然后才发现只是最后多输出一个空行的问题 =。= Orz
/**
* HDOJ 1002 A + B Problem II
* Big Numbers Addition (using String)
* Time Cost : O(n)
* Author: Zheng Chen / Arclabs001
* Copyright 2015 Xi'an University of Posts & Telecommunications. All rights reserved.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//String a and b contains two number and this function compare which one is bigger.
//If a is larger, return true, else false.
bool compare(char *a, char *b, size_t len_a, size_t len_b)
{
if(len_a != len_b)
return len_a > len_b;
for(size_t i=0; i<len_a; i++)
{
if(a[i] != b[i])
return a[i] > b[i];
}
return true;
}
//If a is not larger than b, then swap a and b.
void swap(char *a, char *b, size_t len_a, size_t len_b)
{
char tmp[1002];
memset(tmp,0,sizeof(tmp));
size_t i;
for(i=0; i<len_a; i++)
{
tmp[i] = a[i];
}
tmp[i] = '\0';
for(i=0; i<len_b; i++)
{
a[i] = b[i];
}
a[i] = '\0';
for(i=0; i<len_a; i++)
{
b[i] = a[i];
}
b[i] = '\0';
delete [] tmp;
}
int main()
{
int t;
char a[1002],b[1002],ans[1002];
int numcount = 0;
scanf("%d",&t);
while(t--)
{
numcount++;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(ans,0,sizeof(ans));
scanf("%s %s",a,b);
cout<<"Case "<<numcount<<":"<<endl<<a<<" + "<<b<<" = "; //Just for output format.
if(compare(a,b,strlen(a),strlen(b))==false)
{
swap(a,b);
}
int len_a = (int)strlen(a);
int len_b = (int)strlen(b);
ans[len_a] = '\0';
int i = len_a-1, j = len_b-1;
int carry = 0;
int flag = 0; //If the ans[0] is larger than 10, and only in this case, flag = 1.
for(; i>= len_a - len_b; i--,j--)
{
if(a[i]+b[j]-2*'0'+carry >= 10)
{
ans[i] = a[i]+b[j]-'0'+carry-10;
carry = 1;
}
else
{
ans[i] = a[i]+b[j]-'0'+carry;
carry = 0;
}
if(i==0&&a[i]+b[j]-2*'0'+carry >= 10)
flag = 1;
}
for(; i>0; i--)
{
if(a[i]-'0'+carry >= 10)
{
ans[i] = a[i]+carry-10;
carry = 1;
}
else
{
ans[i] = a[i]+carry;
carry = 0;
}
}
if(len_a!=len_b)
{
if(a[0]+carry-'0' >= 10)
{
flag = 1;
ans[0] = a[0]+carry-10;
}
else
{
ans[0] = a[0]+carry;
}
}
if(flag)
{
cout<<1<<ans<<endl;
}
else
cout<<ans<<endl;
if(t!=0)
cout<<endl;
}
return 0;
}