`
misswolf
  • 浏览: 16900 次
  • 来自: ...
最近访客 更多访客>>
社区版块
存档分类
最新评论

求大数和的两种方案

    博客分类：
  • c++
F#iOSVisioEXT数据结构 
阅读更多

 问题描述:

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>

分享到：
| 我从网上搜来的一篇关于Eclipse上进行C/C+ ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    大数计算器 大数计算器

    在IT领域，大数计算器是一种专门用于处理超出普通计算范围的大整数的工具。这些大数可能达到数百、数千甚至更多的位数，远远超过普通计算机语言内置数据类型的限制。大数计算器通常支持基本的算术运算，如加法、减法...

    C#计算大数的乘法和阶乘

    为了解决这一问题，文中提供了一种新的解决方案，即通过自定义函数来实现大数的乘法运算与阶乘计算。 ### C#中的大数阶乘 #### 阶乘函数实现 首先来看阶乘函数的实现。文中给出的阶乘函数`Factorial`接受一个整数`...

    大数运算\大数高精度计算

    以两个大数A和B为例，首先将这两个数按照位数进行对齐，然后从最低位开始依次相加或相减，并记录进位或借位情况。这一过程类似于小学数学中的竖式加减法。 #### 大数乘法 大数乘法可以采用分治的思想，将一个大数...

    大数除法运算

    一种解决方案是使用动态分配的数组或链表，使得数组长度可以根据需要自动扩展。 总的来说，大数除法是计算科学中的一个重要课题，它在密码学、分布式计算、大数据分析等领域有着广泛的应用。通过巧妙的算法设计和...

    关于c语言百位大数

    在处理大数时，一种常见的方法是使用链表或者数组模拟大数的每一位，而树形结构可以提供更高效的操作，例如快速比较、加减乘除等。 **详细知识点：** 1. **自定义数据结构**：由于C语言没有内置的大数类型，我们...

    大数相乘_大数相乘_python_分治_

    该算法将两个n位数A和B分为两部分：A = a * 10^(n/2) + b，B = c * 10^(n/2) + d，其中a和c是A、B的高位，b和d是低位。根据乘法公式： A * B = (a * 10^(n/2) + b) * (c * 10^(n/2) + d) = a * c * 10^n + (a * d ...

    大数运算的类

    总的来说，大数运算的类是C++中处理大数据量计算的一种解决方案，它扩展了标准整型类型的限制，使得在程序中能够进行任意精度的数学运算。通过理解类的设计和实现，开发者可以更好地掌握高级算法和数据结构，提高...

    大数运算工具C++版

    总之，“大数运算工具C++版”是一个实现大数基础运算的C++库，它提供了一套完整的解决方案，包括大数的存储、加减乘除以及指数和模指幂运算。开发者可以借助此工具，轻松地在C++程序中处理大数问题，而无需关心底层...

    大数的幂运算和幂模运算（加法链和蒙哥马利算法的混合）

    下面将详细阐述这两种算法以及它们如何在大数运算中发挥作用。 首先，让我们了解一下什么是大数。大数是指超过普通计算机原生数据类型（如int或long）所能表示范围的数值。在处理大数时，我们通常会使用一种自定义...

    大数相加通用模版

    《大数相加通用模板》这一主题正是针对此类需求，提供了一种高效、通用的解决方案，尤其适用于ACM竞赛中遇到超出标准数据类型范围的情况。 ### 大数相加的重要性 在计算机科学中，大数运算主要应用于密码学、金融...

    大数四则运算以及比较

    1. **加法**：两个大数相加时，可以将它们看作是两个字符串，按位进行加法操作。从右向左遍历，对每个位进行加法，同时考虑进位。如果某位上的数字超过了9，需要向高位进位。 2. **减法**：减法类似，但需要注意...

    大数相乘通用链表实现

    在编程领域，大数相乘是一项重要的计算任务，特别是在处理金融、加密...总之，链表实现的大数相乘是一种灵活且高效的解决方案，适用于处理大数据量的乘法运算。结合适当的优化技术，它可以为各种计算任务提供强大支持。

    大数除法问题

    本篇文档将详细介绍一种处理大数除法问题的方法——利用数组存储大数，并通过进位来实现运算。这种方法不仅能够有效避免整型变量的取值范围限制，而且具有较高的运算效率。 #### 大数除法实现原理 大数除法的核心...

    大数相乘代码及解析

    这里定义了四个字符数组`ch_one`、`ch_two`、`temp`和`sum`，以及两个变量`length_one`和`length_two`用来存储两个大数的长度。 ##### 4.2 用户输入 ```c printf("\n\tֱ"); printf("\n\t"); scanf("%s",ch_one); ...

    使用java大数做ACM大数题的常用介绍

    Java作为一种广泛使用的编程语言，提供了处理大数的类——`BigInteger`，使得我们可以方便地解决这类问题。本文将详细介绍如何使用Java的大数类来解决ACM中的大数题目。 首先，`BigInteger`是Java `java.math`包下...

    bcd码大数计算源码

    根据提供的文件信息，本文将详细解释“bcd码大数计算源码”的核心概念与实现细节。这段代码主要涉及了BCD(Binary-Coded Decimal，二进制编码十...对于需要处理大数运算的场景来说，这种方法提供了一种可行的解决方案。

    大数剧相加

    通过上述分析可以看出，使用字符数组处理大数是一种有效的解决方案。这种方法的核心在于利用字符数组逐位进行操作，并通过适当的逻辑处理进位，从而实现大数的加法。这种技术不仅适用于加法，还可以扩展到其他算术...

    大数的四则运算（双向链表法）

    双向链表是一种线性数据结构，每个节点包含数据部分和两个指针，分别指向其前一个节点和后一个节点。这种结构允许我们以O(1)的时间复杂度访问相邻节点，便于进行各种操作。 对于大数的存储，我们可以创建一个节点类...

    数据结构课设一：链表实现大数相加

    5. 最后，结果链表就代表了两个大数的和，可以以适当的形式输出，如转化为字符串。 在这个VS2017项目中，`mytest1.sln`是解决方案文件，包含了整个项目的配置信息。`.vs`文件夹是Visual Studio的工作区文件，包含了...

    大数运算+ - * / 和素数检测等

    在编程领域，大数运算和素数检测是两个重要的概念，尤其在处理大规模数据或进行高效计算时。这里我们将深入探讨这两个主题，并结合文件列表，推测这是一个关于C++实现大数运算和素数检测的项目。 首先，让我们来...

Magicbox
Global site tag (gtag.js) - Google Analytics