求大数和的两种方案

 问题描述:

5、大数和(30分)<o:p></o:p>

有一些可能达100位的大正整数，求所有这些数的和。当输入#时，运行结束。

 

样例输入：

9999999999123456789011111234<o:p></o:p>

90000001012301214<o:p></o:p>

111122244413<o:p></o:p>

#<o:p></o:p>

 <o:p></o:p>

样例输出：<o:p></o:p>

9999999999213456901145656861<o:p></o:p>

方案1:
这个是用动态数组的SUM函数就是求两数字串的和
按题意要求可分解为循环求两个数字串的和

Main(){

     建立文件对象

     如果读文件失败则退出程序<o:p></o:p>

     结果=”<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="0" numbertype="1" negative="False" unitname="”" w:st="on">0”</st1:chmetcnv>;<o:p></o:p>

     While(文件是否已读完){

              读入一串数字到str缓冲区;<o:p></o:p>

        结果=Sum(结果,str);<o:p></o:p>

}<o:p></o:p>

打印结果;<o:p></o:p>

}<o:p></o:p>

Char * Sum(char* strLastRes/*上次的结*/,const char* strNum){<o:p></o:p>

   If(IsNumberString(strLastRes)==false&&IsNumberString(strNum)==false)<o:p></o:p>

      Return  “<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="0" numbertype="1" negative="False" unitname="”" w:st="on">0”</st1:chmetcnv>;有一个不为数字串//退出这次加法运算<o:p></o:p>

   Int len1=数字串1长度;<o:p></o:p>

   Int len2=数字串2长度;<o:p></o:p>

   Max=len1>len2?len1:len2;<o:p></o:p>

   Result=new char[Max+1];<o:p></o:p>

   If(Result==NULL) 退出程序; <o:p></o:p>

用’<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="0" numbertype="1" negative="False" unitname="’" w:st="on">0’</st1:chmetcnv>初始化result;<o:p></o:p>

进位标志flat=0;<o:p></o:p>

Char a=0,b=0;<o:p></o:p>

For(i=Max;i>=0;i--){<o:p></o:p>

//从数字串尾逐位往前读数字<o:p></o:p>

        len1--; <o:p></o:p>

         len2--;<o:p></o:p>

     if(len1<0)<o:p></o:p>

         a=0;//字符串1已经取完<o:p></o:p>

     else{<o:p></o:p>

         a=strLastRes[lengthNum1]-'0';<o:p></o:p>

     }<o:p></o:p>

     if(len2<0)<o:p></o:p>

         b=0;//字符串2已经取完<o:p></o:p>

     else<o:p></o:p>

                b=strNum[len2]-'0';<o:p></o:p>

     result[i]=a+b+flag+'0';<o:p></o:p>

if(result[i]-‘<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="0" numbertype="1" negative="False" unitname="’" w:st="on">0’</st1:chmetcnv>>=10){
   result[i]减10;<o:p></o:p>

 进位标志=1;<o:p></o:p>

}else<o:p></o:p>

   进位标志=0;<o:p></o:p>

}<o:p></o:p>

Delete []strLastRes；//释放上次申请的内存<o:p></o:p>

     Return result;<o:p></o:p>

}<o:p></o:p>

ShowResult(const *str){<o:p></o:p>

   Start=pos(str);//第一个不为0位置<o:p></o:p>

   For(i=start;i<strlen(str);i++)<o:p></o:p>

      Cout<<str[i];<o:p></o:p>

}<o:p></o:p>

Bool IsNumberString(const char *str){<o:p></o:p>

  For(i=0;i<strlen(str);i++){<o:p></o:p>

  If(‘<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="0" numbertype="1" negative="False" unitname="’" w:st="on">0’</st1:chmetcnv>≤str[i] ≤’<st1:chmetcnv tcsc="0" hasspace="False" sourcevalue="9" numbertype="1" negative="False" unitname="’" w:st="on">9’</st1:chmetcnv>)

       Continue;

   Else

           Return false;<o:p></o:p>

}<o:p></o:p>

Return true;<o:p></o:p>

}<o:p></o:p>

程序流程序图:如 图五
<o:p></o:p>

<v:shapetype o:spt="75" coordsize="21600,21600" filled="f" stroked="f" id="_x0000_t75" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t"><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path o:extrusionok="f" o:connecttype="rect" gradientshapeok="t"></v:path><o:lock v:ext="edit" aspectratio="t"></o:lock></v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style="WIDTH: 414.75pt; HEIGHT: 8in"><v:imagedata src="file:///C:\DOCUME~1\MissWolf\LOCALS~1\Temp\msohtml1\03\clip_image001.jpg" o:title="ACM5"></v:imagedata></v:shape><o:p></o:p>

图示5<o:p></o:p>

<o:p> 方案二:
用一个结构体存放每一位
struct Node{</o:p>

<o:p> char data;
 Node *next;</o:p>

<o:p>};</o:p>

<o:p>Main()
{</o:p>

<o:p>     Node *pResult=new Node;//假设已运算了一次且结果为0
   pResult->data='0';
  .....</o:p>

<o:p>}
方案二</o:p>

<o:p>在输入时逆向插入结点生成链表也就是说我输入123456789存放到链表时成了987654321运算时就可以顺向往后进行运算了! 得到运算结果后,存放结果的</o:p>

<o:p>链表又成了顺序链表也就是说:假设两个大数的运算结果为1234567那么在一次运算结果的链表时也是1234567</o:p>

<o:p>要想把这个结果参与到下一次运算得把它倒转过来(#-_-#,这样是不是很麻烦)才能参与下一次运算
在输出结果是也得倒转过来!具体看代码吧!这个代码是刚刚写好的,还没有文档的!流程序还没有画的!我的VISIO还没有装的(昨天重装系统了)</o:p>

<o:p>源程序1:#include <fstream>
#include <iostream>
#include <cstdio>
#include <string></o:p>

<o:p>using namespace std;</o:p>

<o:p>char * Sum(char *strLastRes,const char *strNum);
void   ShowResult(const char *str);
int    Pos(const char *Data,char ch);
inline bool   IsNumString(const char *str);
void   TestSum();
int main(int argc, char *argv[])
{
    fstream fileIn("acm5.txt",ios::in);
    if(!fileIn){
        cout<<"load file failed!"<<endl;
        exit(-1);
    }
    char *pStrRes=NULL;//=new char;
    pStrRes="0";
    string str;
    while(!fileIn.eof()){
         fileIn>>str;
   if(str[0]=='#')
    break;
         pStrRes=Sum(pStrRes,str.c_str());
   //pStrRes=Sum(pStrRes,str.c_str());
    }
    ShowResult(pStrRes);
// char* pstrTest="23242423421423412412341234d";
// if(IsNumString(pstrTest)){
//     cout<<"this is number string!"<<endl;
// }
// else{
//  cout<<"not is Number String!"<<endl;
// }
//    cout<<pStrRes<<endl;
// cout<<endl<<"Invoke TestSum Function!"<<endl;
//   TestSum();   
   
 system("PAUSE");
    fileIn.close();
 return EXIT_SUCCESS;
}
char * Sum(char *strLastRes,const char *strNum){
     int lengthNum1=strlen(strLastRes);
     int lengthNum2=strlen(strNum);
  if(IsNumString(strLastRes)==false||IsNumString(strNum)==false)
   return "0";//传入的参数之一不是由数字组成的字符串 既不进入加法运算
//  cout<<"strNum:"<<strNum<<endl;
     int Max=lengthNum1>lengthNum2?lengthNum1:lengthNum2;
     char *result=new char[Max+2];
  result[Max+1]='\0';
     if(result==NULL){
         cout<<"Alloc memory failed!"<<endl;
         exit(-1);
     }
     memset(result,'\0',Max);
     int flag=0;//进位标志
     char a=0,b=0;
     for(int i=Max;i>=0;i--){
          // if(lengthNum1<0||lengthNum2<0)
          //      break;
          // result[i]=(int)result[i]+flag;//加上进位
           lengthNum1--;
           lengthNum2--;
           if(lengthNum1<0)
                a=0;//字符串1已经取完
           else{
                a=strLastRes[lengthNum1]-'0';
           }
           if(lengthNum2<0)
                b=0;//字符串2已经取完
           else
                b=strNum[lengthNum2]-'0';
           result[i]=a+b+flag+'0';
           if((result[i]-'0')>=10){
              result[i]-=10;
              flag =1;
           }else{
              flag=0;
           }
     }
   //  delete [] strLastRes;
   //  strLastRes=NULL;
     return result;
}
void TestSum(){
    char *pStrNum1="1234567898848487848484848484848484848484887454";
    char *pStrNum2="123456234214";
    cout<<"\nin TestSum function!\n"<<endl;
 cout<<pStrNum1<<"+"<<pStrNum2<<" = "<<Sum(pStrNum1,pStrNum2)<<endl;
 }</o:p>

<o:p>void ShowResult(const char *str){
 int len=strlen(str);
 int strPos=Pos(str,'0');
 if(strPos!=-5000){   
  for(int i=strPos;i<len;i++){
    cout<<str[i];
  }
 }
 cout<<endl;
}
int Pos(const char *Data,char ch)
{
    int length_Data=strlen(Data);
    for(int i=0;i<length_Data;i++)
    {
      if(Data[i]!=ch)
        return i;
      else
        continue;
    }
    return -5000;
}
inline bool   IsNumString(const char *str){
 int length=strlen(str);
 for(int i=0;i<length;i++){
  if(str[i]>='0'&&str[i]<='9')
   continue;
  else
   return false;
 }
 return true;
}
</o:p>

<o:p>方案二的源程序:</o:p>

<o:p>#include<iostream>
using namespace std;
struct Node{
 char  data;
 Node *next;
};</o:p>

<o:p>void AddNewNodeBack(Node **pCur);//往前增加结点
void DestoryList(Node *pList);//头结点
bool Sum(Node **pResult,const Node *pListNum);//求两数字串链表和
inline bool IsNumber(char ch);//当前字符是否为数字 内联函数
void ShowList(Node *pList);
void Reverse(Node **pList);
int main(int argc,char*argv[]){
 Node *pListResult=NULL;//保存结果的链表指针
 Node *pListNum=NULL;//用户输入数字的链表指针
 pListResult=new Node;
 pListResult->data='0';//假设已经做了一次加法且结果为0;
 pListResult->next=NULL;
 char ch;
 do{
  ch=getchar();
  if(ch=='#')
   break;
  else{
    while(ch!='\n'){
     if(IsNumber(ch)==false){
      DestoryList(pListNum);//如果输入的不是数字则删除这之前的输入
      pListNum=NULL;
      ch=getchar();//要保证输入的是数字串
      continue;//如果输入的不是数字则进入下一次输入
     }
    //向前添加结点
    AddNewNodeBack(&pListNum);
    pListNum->data=ch;
    ch=getchar();
   }
  }
  Sum(&pListResult,pListNum);//求和
  DestoryList(pListNum);//释放数字链以便下一次输入
  pListNum=NULL;//防止野指针
  Reverse(&pListResult);//倒转一下链表为做下一次运算准备
 }while(1);</o:p>

<o:p> Reverse(&pListResult);//再把结果倒转一次
 ShowList(pListResult);
 cout<<endl;
 DestoryList(pListNum);//释放空间
 DestoryList(pListResult);//释放空间
 return 0;
    //return EXIT_SUCCESS;
}
/* 向前添加结点*/
void AddNewNodeBack(Node **pCur){
 Node *pNode=new Node;
 if(pNode==NULL){
  cout<<"alloc memory failed!\n";
  exit(-1);
 }
 pNode->data='0';
 pNode->next=*pCur;
 *pCur=pNode;
}
void DestoryList(Node *pList){
    Node *pCur=NULL,*pNode=NULL;
 pCur=pList;//指向头结点;
 if(pList!=NULL){//链表不为空则释放内存
  while(pCur!=NULL){
   pNode=pCur;
   pCur=pCur->next;
   delete pNode;
  }
 }
}
/*递归打印链表*/
void ShowList(Node *pList){
 if(pList!=NULL){
  cout<<pList->data;
  if(pList->next!=NULL)
   ShowList(pList->next);
 }
}
bool Sum(Node **pResult,const Node *pListNum){
 if(*pResult==NULL)
  return false;//返回失败
 if(pListNum==NULL)
  return false;//返回失败
 int flag=0;//进位标志;
 Node *pListResult=*pResult;
 Node *pTempCur;
 pTempCur=NULL;
 char a=0,b=0;
 while(*pResult!=NULL||pListNum!=NULL){//当两个链表都读完了，既做完了运算才退出循环
  if(*pResult==NULL)
   a=0;
  else
   a=(*pResult)->data-'0';
  if(pListNum==NULL)
   b=0;
  else
   b=pListNum->data-'0';
  AddNewNodeBack(&pTempCur);//添加一个结点保存当前位的运算结果
  pTempCur->data=a+b+flag+'0';
  if(pTempCur->data-'0'>=10){//如果有进位
   pTempCur->data-=10;
   flag=1;
  }else
   flag=0;
  if((*pResult)!=NULL)
   *pResult=(*pResult)->next;//往下读
  else
   (*pResult)=NULL;
  if(pListNum!=NULL)
   pListNum=pListNum->next;
  else
   pListNum=NULL;
 }
 if(flag==1){//如果两个串链运算有进位
  AddNewNodeBack(&pTempCur);
  pTempCur->data='1';
 }
 DestoryList(*pResult);//释放掉上次的运算结果
 *pResult=pTempCur;
 return true;
 
}</o:p>

<o:p>inline bool IsNumber(char ch){
 if('0'<=ch&&ch<='9')
  return true;
 else
  return false;
}
void Reverse(Node **pList){
 Node *pCur=NULL;
 Node *pTemp=*pList;
 while(*pList!=NULL){
  AddNewNodeBack(&pCur);
  pCur->data=(*pList)->data;
  *(pList)=(*pList)->next;
 }
 DestoryList(*pList);
 *pList=pCur;
}
测试数据:
方案一的测试数据放在文件里
sum.txt文件的内容是</o:p>

<o:p>9999999999123456789011111234
90000001012301214
111122244413
111122244413
111122244413
111122244413
1
99999999991234567890111112343434
#</o:p>

<o:p>方案二的测试数据是从标准输入流输入的</o:p>

<o:p>结果完全正确(#-_-#我也没有做太多的测试)</o:p>

<o:p></o:p>