【例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。