求大数和的两种方案
问题描述:
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="[email protected]@[email protected]@[email protected]@[email protected]@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>