前面我们介绍了大数的相加、相减，我们知道了为什么计算机无法直接做大数的运算，同时我们也知道我们做大数运算程序的方法。本节课，我们介绍大数相乘。

题目：

求两个不超过200位的非负整数的积

【输入】：有两行，每行是一个不超过200位的非负整数，可能有多余的前导0

【输出】：一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342

【样例输入】

50000000000

20000000000

【样例输出】
1000000000000000000000

 

分析：

一、大数乘法与大数加、减法考虑程序不同之处

大数加、减法程序需要考虑的是：进位（借位）怎么处理，进位（借位）后本位怎么处理。但是做大数乘法的时候，考虑到乘数的每一位都要和被乘数的每一位做乘法。这个时候进位和本位处理就复杂化了

二、在做大数乘法的时候需要考虑的问题

1、乘数每位与被乘数每位相乘：所以一定用双层循环来实现

2、每层结果相加的，逐层需要向前移位：结果数组，C[i+j-1] = ?

3、进位与原位处理：

      1）乘积+上次乘积进位+原数（这个原数就是上一层保留在本位的结果，以此完成每层的加法）

      2）计算进位

      3）计算本位剩余的数

      参考代码如下：
 

c[i+j-1]=a[i]*b[i]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;

参考代码：

#include <iostream>
#include <cstring>
using namespace std;

#define N 200
int main() 
{
    
    //定义、初始化
    char a[N],b[N]; //字符数组：两个乘数
    unsigned int A[N],B[N],C[2*N],lena,lenb,lenc,i,j,x;
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    memset(C,0,sizeof(C));
    //输入
    cout<<"please input:";
    cin.getline(a, N);
    cin.getline(b, N);
    //计算乘数、被乘数的长度
    lena = strlen(a);
    lenb = strlen(b);
    //转换为整型，反向存储
    for(i=0;i<lena;i++)
        A[lena-i]=a[i]-'0';
    for(i=0;i<lenb;i++)
        B[lenb-i]=b[i]-'0';
    //开始做大数的乘法
    for(i=1;i<=lena;i++)
    {
        x=0;
        for(j=1;j<=lenb;j++)
        {
            //当前积+上次乘积进位+原数
            C[i+j-1]=A[i]*B[j]+x+C[i+j-1];
            x = C[i+j-1]/10;
            C[i+j-1]%=10;
        }
        C[i+lenb]=x;
    }
    
    lenc=lena+lenb; //相乘之后的最多的位数
    while(C[lenc]==0&&lenc>1)   //删除前导0
    {
        lenc--;
    }
    
    for(i=lenc;i>=1;i--)
    {
        cout<<C[i];
    }
    cout<<endl;
    return 0;
}

 

报名我的信息学竞赛课（C++基础课程、NOIP算法课程、市赛、区赛集训课程），可以加微信????????????????????联系我，注明“姓名+**** 课程咨询”～