欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

高精度计算(四):大整数乘法(采用“万进制”)

程序员文章站 2022-06-14 17:26:20
【例1】大整数乘法。 编写一个程序,求两个不超过200 位的非负整数的积。 (1)编程思路。 大整数乘大整数,实质就是在小学竖式乘法的基础上枚举各个乘数位与被乘数相乘,累加到结果当中。其中乘数中的第j位与被乘数中的第i位相乘时,结果应该保存到结果的第i+j-1位中。 (2)源程序。 #include ......

【例1】大整数乘法。

      编写一个程序,求两个不超过200 位的非负整数的积。

      (1)编程思路。

      大整数乘大整数,实质就是在小学竖式乘法的基础上枚举各个乘数位与被乘数相乘,累加到结果当中。其中乘数中的第j位与被乘数中的第i位相乘时,结果应该保存到结果的第i+j-1位中。

      (2)源程序。

#include <iostream>
using namespace std;
const int base=10000;
const int maxlen=50+2;
void chartobignum(char *ch,int *bignum)
{
      int len,i,j,p,num;
      memset(bignum,0,sizeof(int)*maxlen);
      len=strlen(ch);
      bignum[0]=len%4==0?len/4:len/4+1;
      i=1;
      while (i<=len/4)
      {
          num=0;
          p=len-4*i;
          for(j=1;j<=4;j++)
              num=num*10+(ch[p++]-'0');
          bignum[i]=num;
          i++;
       }
       if (len%4!=0)
       {
            num=0;
            for (i=0;i<=len%4-1;i++)
                 num=num*10+(ch[i]-'0');
            bignum[len/4+1]=num;
        }
}
void printbignum(int *bignum)
{
       int *p=*bignum+bignum;
       cout<<*p--;
       cout.fill('0'); // 定义填充字符'0'
       while(p>bignum)  { cout.width(4); cout<<*p--; }
       cout<<endl;
}
void multiply( int *bignum1, int *bignum2, int *bignum_ans)
{
      int carry=0, i, j;
      memset(bignum_ans, 0, sizeof(int)*2*maxlen);
      for (j=1; j<=bignum2[0]; j++){
           for(i=1; i<=bignum1[0]; i++){
               bignum_ans[i+j-1]+=carry+bignum1[i]*bignum2[j];
               carry=bignum_ans[i+j-1]/base;
               bignum_ans[i+j-1]%=base;
            }
            i=j+bignum1[0];
            while(carry){
                 bignum_ans[i++]=carry%base;
                carry/=base;
            }
       }
       bignum_ans[0]=bignum1[0]+bignum2[0];
       while( !bignum_ans[*bignum_ans] ) --bignum_ans[0];
}
int main()
{
       int bignum1[maxlen],bignum2[maxlen],bignum_result[2*maxlen];
      char numstr[maxlen];
      cout<<"请输入第1个大整数:";
      cin>>numstr;  
      chartobignum(numstr,bignum1);
      cout<<"请输入第2个大整数:";
      cin>>numstr;
      chartobignum(numstr,bignum2);
      multiply(bignum1,bignum2,bignum_result);
      cout<<"两个大整数的积是 :";
      printbignum(bignum_result);
      return 0;
}

      将上面源程序中的输入输出提示语句删除后,提交给poj 2389 “bull math”,可以accepted。