随笔-145  评论-173  文章-70  trackbacks-0
最近看很多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 *= 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 *= new int [maxNum];
     
int *= new int [aNum];
     
int *= 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 阅读(5096) 评论(2)  编辑 收藏 引用 所属分类: ACM

评论:
# re: 杭电ACM 1002题--大数加法 2011-06-13 17:49 | 路人
写得不好
思路不清
看刘汝佳的白书吧
入门起点不能太低  回复  更多评论
  
# re: 杭电ACM 1002题--大数加法 2011-06-14 21:42 | 刘畅
@路人
谢谢,目前正在看,争取先做些水题来入手下。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理