最近看很多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 閱讀(5225)
評論(2) 編輯 收藏 引用 所屬分類:
ACM