大数四则运算的C++实现2(转)

文件:	大数四则运算的C++实现(转) .rar
大小:	14KB
下载:	下载

2.3 乘法运算的实现

    首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加。得出最后结果。当然我们可以直接用这种方法，但要用多个链表来保存计算出的分结果，之后结果再相加得到最后结果，但是这样会浪费很多空间，我们可以再优化一下，就是只用一人链表来表示结果，先把第一位乘数与被乘数的结果保存在链表中，之后把存储结果的头部后移一位、也就是从链表的第二加起，当第二位乘数与被乘数结果加到第二之后的各个项内。以此类推，直到结束。这样就可以用一个链表来存储相乘后的结果。

    在程序时应注意：

    1、传入的乘数和被乘数是以字符串形式放入的话，要让指针指向最后一位，我自己写了个函数来完成这件事。链表传入也要找到最后一向来计算；

    2、因为传入和保存的都是字符，所以计算时要将字符转化为数字，算完再转化为字符存储；

    3、另外进位时要处理，当前的值加上进位的值再看本位数字是否又有进位；

    4、输出时要逆序输出，因为链表首指针是存的结果的最低位。我的函数为了对应输入输出结果的一致性，都有采用了字符串输出，所以在输出时又将链表转为了字符串。

    具体代码如下：

/*--------------------------------------------------------------------------

*函数名称： 大数乘法

*函数过程：1 输入两个大数作为字符串

* 2 作一个双向链表

* 3 两个指针分别指向数字字符串的最低位

* 4 以第一个数的最低的一个位乘以第二个数的所有项存于链表中

* 5 链表首指针移

* 6 重复4，5依次从最低位乘到最高位

* 7 乘完后因为最低位是链表首，最后一位是链表尾。所以在逆顺输出链表。

* 4 直到循环结束

*入口参数：numa，numb，result字符串

*出口参数：无

*--------------------------------------------------------------------------*/

void multiply(char *numa, char *numb ,char *result)//用来储结果的)//计算乘积

{

 char *pna = findend(numa);//指向numa的一个指针。point numa      pna 指向乘数的最低位，

 char *pnb = findend(numb);//指向numb的一个指针                 //pnb 指向被乘数的最低位，

 int along=(int)strlen(numa);//标记数字a的长度；

 int blong=(int)strlen(numb);//标记数字b的长度；

 int  carry=0,temp_result;//存贮进位  和临时结果的

 Node *head,   // 用于存贮头指针

  *pstart,  // 用于存贮计算时的首指针

  *pnew,    //作于申请新结点 

  *pgo;     //作为每计算完一行时，回到下一行起始节点用,移位标致来用

 head = pstart =new Node;//初始化首结点和头结点。

 pstart -> data = 0;

 pstart -> next = NULL;

 pstart -> ahead = NULL; 

 while (along--)

 {

  pgo = pstart;//保存进位点

  blong = (int)strlen(numb);//初始化长度

  pnb = findend(numb); //初始化指针

  while ((blong-- && (blong>=0))|| carry != 0)

  {    

   if(!pstart->next)//如果当前为空结点，则申请新结点

   {

    pnew = new Node;

    pnew -> data = 0;

    pnew -> next = NULL;

    pnew -> ahead = pstart;

    pstart -> next = pnew;

   }

   if(blong<0)temp_result = carry ;//处理只有进位的情况

   else temp_result =(pstart->data+(*pna-48)*(*pnb-48)+carry);//自身值+新值+进位作为新值   

pstart -> data = temp_result%10;  //存贮个位

   carry = temp_result/10;           //存贮进位

   pstart = pstart -> next;          //结点移动         

   pnb--; //指针移向被乘数高位

  }

  pstart = pgo->next; //前进一个位置；

  pna--;   //指针移向乘数高位

 }

 pstart =head;//寻找链表的结尾点

 while(pstart->next != 0)

 {

 pstart->data += 48;//!!<<<因为我们的输出是字符。所以再此加上48>>>>  逆顺输出

 pstart = pstart->next ;

 }

    int tip = 0;//转为字符串用

 pstart = pstart->ahead ;//找有效字

 while(pstart != 0)//输出正序的结果；

 {

    result[tip++] = pstart->data; 

 pstart = pstart->ahead ;

 }

 result[tip] = '\0';

 pstart =head;  //释放空间

 while(pstart->next != 0)

 {

 pnew = pstart->next ;delete pstart;

 pstart =pnew; 

 }

   return ;

}

 

2.4 除法运算的实现

    首先说一下我们所要的结果，当除数除不开被子除数时，不用除到小数，当除数小于被除数时，除数作为余数既可，不用再向下除了。

    除法算法是最容易想到的啦！我们学数字电路，或模拟电路时里面有用门实现的除法器，做法是用除数减被除数，再用一个加法器去计算存储结果，算法简单明了，结果我实现之后，计算速度大大出乎我的遇料，比算乘方时还慢，经仔细想想电路中计算的长度不过8位，16位，32位，而且都是硬件实现，我们要算的是几千位，几万位。特别是两数位长度差很大时计算速度相当慢，如10000-3时要进行多少次链表运算啊。

    否定了这条算法，经不断思考，发现另一种方法可行，且效率仅次于减法。就是从高位向低位减，减时以被除数长度为单位，从高位取出大于被除数的字符串，和被除数相减，减的次数为结果，余数从剩下的除数高位再取出几位做补位，直到大于被除数。再减，循环减到被减数大于余数加上补位，那么这个新的余数作为结果返回。

    在程序时应注意：

    1、除法算法计算时是用的最高位开始向低位减，所以要注意指针的位置。

    2、余数和被减数相减时，一定要注意：一旦能够减开被除数时，一定要每从除数那里取一个字符时，结果也要对应补一个0。如111222/111。

/*--------------------------------------------------------------------------

*函数名称： 大数除法2-- 

*函数想法：1 用指针指向除数的最高位，保存临时字符串； tempstr[a++] = pna

* 2 如果临时字符串大于被除数，则相减。结果等于余数

* if(tempstr>numb)tempstr = tempstr - numb

* 3 如果小于被除数且指针到头，余数 等于 临时字符串

* if(tempstr * 

*入口参数：numa，numb，result,remainder字符串

*出口参数：无

*--------------------------------------------------------------------------*/

void divide2( char *numa, char *numb,char *result,char *remainder)//计算除法2

{

 char one[]="1";//临时字符串....

    char one2[]="1";//

 char zero[]="0";//

 char numb2[6048];//

 char tempstr[6018]="";//临时字符串

 int  ia=0,ia2=0;//tempstr的指示器

 bool  moveon=false;//翻转牌

    char *pna = numa;//指向numa的一个指针。point numa      pna 指向减数的最低位，

 char *pnb = findend(numb);//指向numb的一个指针                 //pnb 指向被减数的最低位，

 Node *head,   // 用于存贮头指针

  *pstart,  // 用于存贮计算时的首指针

  *pnew;    //作于申请新结点 

  

 head = pstart =new Node;//初始化首结点和头结点。

 pstart -> data = 0;

 pstart -> next = NULL;

 pstart -> ahead = NULL; 

 moveon = false;

 while(*pna)

 {

     if(!pstart->next)//如果当前为空结点，则申请新结点

  {

   pnew = new Node;

   pnew -> data = 0;

   pnew -> next = NULL;

   pnew -> ahead = pstart;

   pstart -> next = pnew;

  }

 

        ia=(int)strlen(tempstr);//取的长度

   tempstr[ia++] = *(pna++);    

 

        tempstr[ia] ='\0'; //转换为字符串

   if(tempstr[0]=='0')//处理高位也是0的那种 如00

   {

    ia2=0;

    while(tempstr[ia2]=='0')++ia2;

     while(ia2>=1)//清除无用的0

     {

      ia=ia2-1;

      tempstr[ia]=tempstr[ia2];

      --ia2;

     }

     tempstr[++ia2]='\0'; 

   }

  while(abigerb(tempstr,numb)>0)//如果tempstr大于等于numb

  {    

   if(tempstr[0]=='0')//处理高位也是0的那种 如00----此乃冗余代码，留做记念用            

{

    ia2=0;

    while(tempstr[ia2]=='0')++ia2;

    if(ia==ia2 )

    {

    moveon = true;

     break;

    }

   }

   strcpy(numb2,numb);

   subtract(tempstr, numb,tempstr);//A-B

   strcpy(numb,numb2);

   if(tempstr[0]=='-')//若判断的不准，变为了负数就再加上B。。   

{

    strcpy(numb2,numb);

    addition(tempstr, numb,tempstr);//A-B

    strcpy(numb,numb2);

    ia2=0; //修正之后的长度。因为加法中未做负数运算

ia=0;  //为了消除最后的那一个负号，整体向前移动。

    while(tempstr[ia2]!='\0')++ia2;     

    while(ia2>=1)//清除无用的0

     {

      tempstr[ia]=tempstr[ia+1];

      ++ia;

      --ia2;

     }

     tempstr[ia]='\0'; 

    moveon = true;

    break;

   }

   pstart->data++ ; //结果自加

            moveon = true;

  }

  if(moveon) pstart = pstart -> next;          //结点移动

 }

 strcpy(remainder,tempstr);//存贮余数

    int tip = 0;//转为字符串用

 pstart =head;//寻找链表的结尾点

 while(pstart->next != 0)

 {

 pstart->data += 48;//!!<<<因为我们的输出是字符。所以再此加上48>>>>  逆顺输出

 result[tip++] = pstart->data; 

 pstart = pstart->next ;

 }

 result[tip] = '\0';//存贮结果

 pstart =head;  //释放空间

 while(pstart->next != 0)

 {

 pnew = pstart->next ;delete pstart;

 pstart =pnew; 

 }

   return ;

}

 

2.5 幂运算的实现

    幂的实现是最为简单的了，国为有了前面的算法做铺垫，就是调用乘法函数，来循环去自乘，幂指数相应减1，直到幂指数变为0时结束。其详细代码如下：

/*--------------------------------------------------------------------------

*函数名称： 大数幂

*函数想法：1 B自减1直到，，作为循环控制变量.保存结果； 

* 2 结果初值1 每次乘以A

* 3 重复1、2步骤到结束. 

*入口参数：numa，numb，result字符串

*出口参数：无

*--------------------------------------------------------------------------*/ 

void power (char *numa, char *numb,char *result) //计算幂 

{ char one[]="1"; //临时字符串.... 

char one2[]="1"; 

char zero[]="0"; 

char numb2[6048]; 

char remainder[6048]; 

strcpy(result,one); //给结果初值为1 

strcpy(numb2,numb);

subtract(numb,one ,remainder); //B自减1 

strcpy(numb,numb2);

strcpy(numb2,numb);

multiply(result,numa,result ); //A自己乘自己 

strcpy(numb,numb2); 

while(strcmp(remainder,zero)>0) //A大于相等B时 就是numb不等于0时 

{

strcpy(numb2,numb);

multiply(result,numa,result ); //A自己乘自己 

strcpy(numb,numb2); 

strcpy(one,one2);

subtract(remainder,one ,remainder); //B减一 

}

return ;

}

 3. 程序运行介面 

    程序的介面制作就不多加描述了，以下是我的大数程序的运行介面。

 

4. 总结与评价 

    1) 本文主旨是对算法加以了实现，但未做相应的优化。因为本文的目地是对大数运算的过程产生一个具体设计方法与实现思路。而还是不是工程上能所直接应用的。当然在要作中是也许用的设计语言并不是C语言，可能是JAVA、 C++、 Delphi 、PHP等等。但不管是什么样的设计语言，设计思路都是相同的。

    2) 关于代码和算法优化问题，本文中代码并不是简短，高效。现在对此说明个人认为在工程要改正的几个方面。首先每个链表节点的元素所存的数据小的可怜，只存储了一位数据，但这是最容易想到的，模仿十进制那样进位。但这并没考虑机器的计算的情况，在我们常用的32位计算中，CPU中加减乘除的一次运算是32位的值，也就是说2的32次方的一个值，这就是说1加上1的CPU工作量和小于2的32的两位数相加是用的相同的周期。如下图所示:

    为避免运算结果大于2的32次，因为大于的话又会造成一次CPU周期运算，但这样当然也可以做。但建议用下面方法，考虑乘法的原因，两个2的16次方相乘就是2的32次方的情况，所以我们可以定义每个链表节点值为2的16次方，也就是 18446744073709551616的一个整数值，C++语言中_int64类型的范围就是这么大。再把它当作以前处理十进制的权10去处理，效率会翻2的16方倍了。结点数巨减，主要是开内存方面，有了极大的减少。

    3) 另外本程序中是用数组去传递参数的，这非常不好，而且会限制你结果的长度。只有一点好处，易懂！个人认为工程中，一定要用链表指针来传递参数， 这样就解决了可算到无限长的问题。只是释放链表时要在最后用完再释放了。对于本文用的方法就显得明了多了。

    4) 总体来说本文重在说明方法，效率较差。工作时定要注重效率问题。在C++系列下的程序尽量多用库函数，会减少大量的代码。适当的去加入些汇编以提高效率。

5. 软件下载演示 

6. 参考文献 

1. 李艺《网络安全讲义》PPT文档

2. 谭浩强《C程序设计》第二版,清华大学出版社

3. Adam Drozdek《数据结构与算法》第三版,清华大学出版社

4. 何德全《网络安全》清华大学出版社

5. 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/lishuiwang/archive/2009/10/05/4634756.aspx