当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 高精度计算（二）：大整数乘法

高精度计算（二）：大整数乘法

2019年07月16日  | 移动技术网IT编程  | 我要评论

法语翻译器,艾雅康,女生奇葩辞职信

【例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）源程序。（将此源程序提交给poj 2389 “bull math”，可以accepted）

#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[i] - '0';
     n2 = strlen(b);
     j = 0;
    for (i = n2 - 1;i >= 0 ; i --)
        num2[j++] = b[i] - '0';
    for (i=0;i < n2; i++ )
    {
        for (j=0; j<n1; j++)
            result[i+j] += num2[i]*num1[j];   // 两数第i, j 位相乘，累加到结果的第i+j 位
    }
     //  统一处理进位问题
    for( i = 0; i < max_len * 2; i ++ ) {
         if (result[i] >= 10)
         {
              result[i+1] += result[i] / 10;
              result[i] %= 10;
         }
    }
    bool isbeginzero = false;
    j=0;
    for (i=n1+n2-1; i>=0; i--)
         if (isbeginzero)
            c[j++]=result[i]+'0';
        else if (result[i]!=0)
        {
             c[j++]=result[i]+'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[i] - '0';
      n2 =0;
      t=b;
      do {
           n2++;
           t=t/10;
       } while (t!=0);
       for (i=0;i < n1; i++)
            result[i] = num[i]*b;
       //   统一处理进位问题
       for (i = 0; i < n1+n2; i++)
       {
            if (result[i] >= 10)
           {
                result[i+1] += result[i] / 10;
                result[i] %= 10;
            }
       }
      bool isbeginzero = false;
      j=0;
      for (i=n1+n2-1; i>=0; i--)
          if (isbeginzero)
             c[j++]=result[i]+'0';
         else if (result[i]!=0)
        {
            c[j++]=result[i]+'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;
}

 【例2】exponentiation  （poj 1001）。

description

problems involving the computation of exact values of very large magnitude and precision are common. for example, the computation of the national debt is a taxing experience for many computer systems.

this problem requires that you write a program to compute the exact value of rn where r is a real number ( 0.0 < r < 99.999 ) and n is an integer such that 0 < n <= 25.
input

the input will consist of a set of pairs of values for r and n. the r value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
output

the output will consist of one line for each line of input giving the exact value of r^n. leading zeros should be suppressed in the output. insignificant trailing zeros must not be printed. don't print the decimal point if the result is an integer.
sample input

95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
sample output

548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

      （1）编程思路。

      由于输入的r可能是一个小数，因此先求出r的小数点后有多少位小数（pos），然后将小数点去掉，使得r变成一个整数，然后采用例1中的函数void bignummul(char a[],char b[],char c[])用循环求得rn 。之后，在结果中正确插入小数点即可。

      （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[i] - '0';
     n2 = strlen(b);
     j = 0;
     for (i = n2 - 1;i >= 0 ; i --)
         num2[j++] = b[i] - '0';
     for (i=0;i < n2; i++ )
    {
          for (j=0; j<n1; j++)
               result[i+j] += num2[i]*num1[j]; 
     }
     for( i = 0; i < max_len * 2; i ++ ) {
          if (result[i] >= 10)
          {
               result[i+1] += result[i] / 10;
               result[i] %= 10;
           }
      }
      bool isbeginzero = false;
      j=0;
      for (i=n1+n2-1; i>=0; i--)
          if (isbeginzero)
             c[j++]=result[i]+'0';
          else if (result[i]!=0)
          {
              c[j++]=result[i]+'0';
              isbeginzero = true;
          }
     if (!isbeginzero) c[j++]='0';
    c[j]='\0';
}
void insertpoint(char s[],int pos,int n)
{
      int len,i,j;
      if (pos==0) return;
      len = strlen(s);
      if (len<=pos*n) // 乘积全为小数部分
      {
           s[pos*n+1]='\0';
           for (i=len-1,j=pos*n;i>=0;i--,j--)
                s[j]=s[i];
           for (i=j;i>0;i--)
                s[i]='0';
           s[0]='.';
      }
      else // 小数点位于乘积中间
      {
           s[len+1]='\0';
           for (i=len,j=1; j<=pos*n; i--,j++)
                 s[i]=s[i-1];
          s[i]='.';
      }
      for (i=strlen(s)-1; i>=0; i--)
      {
            if (s[i]=='0')
                s[i] ='\0';
            else
                break;
       }
       if (s[strlen(s)-1]=='.') s[strlen(s)-1]='\0';
}
int main()
{
      char s[max_len],result[2*max_len];
      int n,i,flag,pos,len;
      while(scanf("%s%d",s,&n)!=eof)
      {
          flag = 0;
          len = strlen(s);
          pos=0;
          for (i=0; i<len;i++) // 寻找小数点位置，并去掉小数点
          {
              if(s[i]=='.')
              {
                   flag = 1;
                   pos = len - i - 1;
              }
              s[i] = s[i+flag];
           }
           strcpy(result,s);
           for (i=1;i<n;i++)
                 bignummul(result,s,result);
            insertpoint(result,pos,n);
            printf("%s\n",result);
       }
       return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网