最近看很多ACM大牛，感觉自己在算法方面很菜，为此有时间做做ACM题目吧，从最简单的开始，慢慢搞。
昨天看到了杭电ACM的1002题，然后想了会，把大数的加法部分做了，然后今天具体就完成了输入和计算的处理模块。提交了几次都出现了presentation error问题，发现对于结果的格式要求还是很严格的。为此修改了几次，终于过了。发现通过率才18%，还是有点自豪感，虽然比较菜，但是还是慢慢搞吧。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int *sum(int *a,int aNum,int *b,int bNum,int &FirstFlag)//人为的让左边数组较长(大)
{
int maxNum = aNum;
int *c = new int [maxNum]; //可能有进位
int flag = 0;
for(int i = 0; i < maxNum; i++)
{
if(i < bNum )
{
if( (a[aNum - i - 1] + b[bNum - i - 1] + flag) >= 10 )
{
c[aNum - i - 1] = a[aNum - i - 1] + b[bNum - i - 1] + flag - 10;
flag = 1; //flag一定是在计算之后得到的
}
else
{
c[aNum - i - 1] = a[aNum - i - 1] + b[bNum - i - 1] + flag;
flag = 0;
}
}
else
{
if( (a[aNum - i - 1] + flag) >= 10)
{
c[aNum - i - 1] = a[aNum - i - 1] + flag - 10;
flag = 1;
}
else
{
c[aNum - i - 1] = a[aNum - i - 1] + flag;
flag = 0;
}
}
}
if(flag == 1)
FirstFlag = 1;
return c;
}
int main()
{
int number;
cin >> number;
int i = 0;
string a,b;
vector<string> vec;
while(i < number)
{
cin >> a >> b;
vec.push_back(a);
vec.push_back(b);
i++;
}
for(i = 0; i < number; i++)
{
// cout << vec[2 * i] << " "<< vec[2 * i + 1] << endl;转换成数组
int aNum = vec[2 * i].length();
int bNum = vec[2 * i + 1].length();
int maxNum = (aNum > bNum) ? aNum : bNum;
int *c = new int [maxNum];
int *a = new int [aNum];
int *b = new int [bNum];
for(int k = 0; k < aNum; k++)
{
a[k] = vec[2 * i].at(k) - '0';
}
for(int j = 0; j < bNum; j++)
{
b[j] = vec[2 * i + 1].at(j) - '0';
}
int FirstFlag = 0;
if(aNum > bNum)
{
c = sum(a,aNum,b,bNum,FirstFlag);
cout << "Case " << i+1 << ":" << endl;
cout << vec[2 * i] << " + " << vec[2 * i + 1] << " = ";
if(FirstFlag == 1)
cout << FirstFlag ;
for(int m = 0; m < aNum; m++)
cout << c[m];
cout << endl;
if(i != (number-1))
cout << endl;
}
else
{
c = sum(b,bNum,a,aNum,FirstFlag);
cout << "Case " << i+1 << ":"<< endl;
cout << vec[2 * i] << " + " << vec[2 * i + 1] << " = ";
if(FirstFlag == 1)
cout << FirstFlag ;
for(int m = 0; m < bNum; m++)
cout << c[m];
cout << endl;
if(i != (number-1))
cout << endl;
}
delete []a;
delete []b;
delete []c;
}
return 0;
}
总结来说就是：
（1）先从一个个模块开始吧，比如大数加法函数，然后再考虑输入格式，读取，输出等等其他。
（2）大数的话还是有很多要考虑的，进位的问题，补齐等问题，开始写这个函数的时候都没有注意到，真够菜的，改了几遍才过。
（3）效率啥的觉得不高，各位能够优化的欢迎交流，另外关于ACM有兴趣的同学可以讨论下，我才刚入门，欢迎指教。
posted on 2011-06-12 20:09
deercoder 阅读(5167)
评论(2) 编辑 收藏 引用 所属分类:
ACM