高精度计算之大整数乘法【黑马C++培训】

【例1】两个大整数乘法。

      输入两个不超过200位的非负大整数a和b，求a×b的值。

      （1）编程思路。

      用 unsigned num1[200]和num2[200]分别存放两个乘数，用result[400]来存放积。计算的中间结果也都存在result 中。result 长度取400 是因为两个200 位的数相乘，积最多会有400 位。num1[0], num2[0], result[0]都表示个位。

       计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将 进位问题留待最后统一处理。

       图1给出了753×68的计算过程。描述如下：

      1）先依次计算753的各位数字与8的乘积，并加到result数组的相应单元中。result数组的全部元素的初始值均为0。

      2）再依次计算753的各位数字与6的乘积，并加到result数组的相应单元中。

      3）乘法过程完毕。从 result[0]开始向高位逐位处理进位问题。result[0]留下4，

把2 加到result[1]上，result[1]变为60 后，应留下0，把6 加到result[2]上……最终使 得result 里的每个元素都是1 位数，结果就算出来了。

       在乘法过程中，num1的第i 位和num2的第j 位相乘所得的数，一定是要累加到 result的第i+j 位上。这里i, j 都是从右往左，从0 开始数。

      （2）源程序。

#include <stdio.h> #include <string.h> #define MAX_LEN 201 void bigNumMul(char a[],char b[],char c[]) {       int i,j,n1,n2;       int num1[MAX_LEN]={0},num2[MAX_LEN]={0},result[2*MAX_LEN]={0};       // 将a和b中存储的字符串形式的整数转换到num1和num2中去，       // num1[0]对应于个位、num1[1]对应于十位、……       n1 = strlen(a);       j = 0;      for (i = n1 - 1;i >= 0 ; i --)         num1[j++] = a - '0';      n2 = strlen(b);      j = 0;     for (i = n2 - 1;i >= 0 ; i --)         num2[j++] = b - '0';     for (i=0;i < n2; i++ )     {         for (j=0; j<n1; j++)             result[i+j] += num2*num1[j];   // 两数第i, j 位相乘，累加到结果的第i+j 位     }      //  统一处理进位问题     for( i = 0; i < MAX_LEN * 2; i ++ ) {          if (result >= 10)          {               result[i+1] += result / 10;               result %= 10;          }     }     bool isBeginZero = false;     j=0;     for (i=n1+n2-1; i>=0; i--)          if (isBeginZero)             c[j++]=result+'0';         else if (result!=0)         {              c[j++]=result+'0';               isBeginZero = true;          }     if (!isBeginZero) c[j++]='0';     c[j]='\0'; } int main() {      char a[MAX_LEN],b[MAX_LEN],c[2*MAX_LEN];      scanf("%s",a);      scanf("%s",b);      bigNumMul(a,b,c);      printf("%s\n",c);      return 0; }

（3）问题扩展。

下面我们来讨论如何完成一个大整数a和一个int型整型变量b的相乘。

图2给出了753×68的另一种计算过程。描述如下：

      

       1）先依次计算753的各位数字与68的乘积，并存入到result数组的相应单元中。

       2）乘法过程完毕。从 result[0]开始向高位逐位处理进位问题。result[0]留下4，

把20 加到result[1]上，result[1]变为360 后，应留下0，把36 加到result[2]上……最终使 得result 里的每个元素都是1 位数，结果就算出来了。

按这个思路可以实现一个大整数与int型整型变量相乘。源程序如下：

#include <stdio.h> #include <string.h> #define MAX_LEN 201 void bigNumMul(char a[],int b,char c[]) {       int i,j,n1,n2,t;       int num[MAX_LEN]={0},result[MAX_LEN+10]={0};       // 将a和b中存储的字符串形式的整数转换到num1和num2中去，       // num1[0]对应于个位、num1[1]对应于十位、……       n1 = strlen(a);       j = 0;       for (i = n1 - 1;i >= 0 ; i --)          num[j++] = a - '0';       n2 =0;       t=b;       do {            n2++;            t=t/10;        } while (t!=0);        for (i=0;i < n1; i++)             result = num*b;        //   统一处理进位问题        for (i = 0; i < n1+n2; i++)        {             if (result >= 10)            {                 result[i+1] += result / 10;                 result %= 10;             }        }       bool isBeginZero = false;       j=0;       for (i=n1+n2-1; i>=0; i--)           if (isBeginZero)              c[j++]=result+'0';          else if (result!=0)         {             c[j++]=result+'0';             isBeginZero = true;          }        if (!isBeginZero) c[j++]='0';        c[j]='\0'; } int main() {       char a[MAX_LEN],c[MAX_LEN+10];        int b;       scanf("%s",a);        scanf("%d",&b);        bigNumMul(a,b,c);        printf("%s\n",c);        return 0; }