超哥的小学期中考试
时间: 1ms 内存:128M
描述:
一听说期中考试来了,超哥兴高采烈地想要对自己这么久以来的学习进行一次检验,超哥兴奋地秒杀了前五道题,来到了第六道题,“a+b”。这是一道100000位数以内的加法计算题,可超哥只用了1秒就将它算出,你知道他怎么做的吗?(为了简单起见,a,b均为正整数,且超哥透露了他自己的部分思路,即给出代码前缀与后缀,补全中间部分,提交时只提交中间部分即可)
输入:
输入包含多组数据,
每行输入包含两个长度不大于100000位的正整数 输入以0 0结束
输出:
输出相加之后的答案
示例输入:
1
1
2222222222
8888888888
0
0
示例输出:
2
11111111110
提示:
参考答案(内存最优[1852]):
#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;
class number
{
public:
friend istream &operator>>(istream &in,number &n)
{
in>>n.num;
return in;
}
friend ostream &operator<<(ostream &out,number &n)
{
return out;
}
friend bool flag_stop(number a,number b);
number operator +(number n);
private:
char num[MAX];
};
bool flag_stop(number a,number b)
{
if(a.num[0]=='0'&&b.num[0]=='0')return true;
else return false;
}
void reverse(char n[])
{
int len=strlen(n);
for(int i=len-1;2*i>len-1;i--)
{
swap(n[i],n[len-1-i]);
}
}
void num_add(char n1[],char n2[],char result[])
{
reverse(n1);
reverse(n2);
int i;
int len1=strlen(n1);
int len2=strlen(n2);
int min=len1<=len2?len1:len2;
int max=len1>len2?len1:len2;
for(i=0;i<min;i++)
{
result[i]=n1[i]+n2[i]-'0';
}
for(i=min;i<max;i++)
{
result[i]=len1>len2?n1[i]:n2[i];
}
for(i=0;i<max-1;i++)
{
result[i]-='0';
if(result[i]>9)
{
result[i+1]+=result[i]/10;
result[i]%=10;
}
result[i]+='0';
}
int k=max-1;
int last=result[max-1]-'0';
while(last)
{
result[k++]=last%10+'0';
last/=10;
}
result[k]=0;
reverse(result);
cout<<result;
}
number number::operator+(number n)
{
number s;
num_add(num,n.num,s.num);
return s;
}
int main()
{
number a,b;
while(cin>>a>>b)
{
if(flag_stop(a,b))break;
number c=a+b;
cout<<c<<endl;
}
return 0;
}
参考答案(时间最优[16]):
#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;
class number
{
public:
friend istream &operator>>(istream &in,number &n)
{
in>>n.num;
return in;
}
friend ostream &operator<<(ostream &out,number &n)
{
out<<n.num;
return out;
}
friend bool flag_stop(number a,number b);
number operator +(number n);
private:
char num[MAX];
};
bool flag_stop(number a,number b)
{
if(a.num[0]=='0'&&b.num[0]=='0')return true;
else return false;
}
#include<algorithm>
number number::operator+(number n)
{
number cnt;
memset(cnt.num,0,sizeof(cnt.num));
int len1 = strlen(num);
for(int i=0; i<len1; i++)
num[i]-='0';
int len2 = strlen(n.num);
for(int i=0; i<len2; i++)
n.num[i]-='0';
reverse(num,num+len1);
reverse(n.num,n.num+len2);
int len = max(len1,len2);
for(int i=0; i<len; i++)
{
cnt.num[i] += num[i]+n.num[i];
if(cnt.num[i]>=10)
{
if(i==len-1)len++;
cnt.num[i+1]+= (cnt.num[i])/10;
cnt.num[i]%=10;
}
}
for(int i=0; i<len; i++)
cnt.num[i]+='0';
reverse(cnt.num,cnt.num+len);
return cnt;
}
int main()
{
number a,b;
while(cin>>a>>b)
{
if(flag_stop(a,b))break;
number c=a+b;
cout<<c<<endl;
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。