题解

难度：中等

知识点：数学逻辑

方法一：普通竖式

模拟数学中两个数相乘的步骤和思路，如图所示num1=123，num2=45

可以看到
1）num1的长度为L1，num2的长度为L2,那么乘积结果res的长度最长为L1+L2，因为结果的最高位的产生是num2的最高位与num1最高位的乘积的首位，所以res的长度为L1+L2-1，或者L1+L2
2）步骤：
从num2的末位循环到首位，每位都与num1相乘，乘的结果要与res已存的结果相加。num2中数字的位置决定了该数与num1相乘的结果向左的移位，例如num2中的4，与num1的结果为492，但是492在与res相加时，是向左移了一位。

#include<iostream>
#include<string>
using namespace std;
//移位进位法
string Mul(string num1, string num2)
{

    size_t L1 = num1.size();
    size_t L2 = num2.size();
    size_t Size = L1 + L2;
    string res(Size, '0');

    int takevoer = 0;//进位，这个是最后都是相加，所以存的进位
    int offset = 0;//移位，是right的位数代表整个结果在相加前向左的移位

    size_t idx = 1, j = 1;
    //right从末位循环到首位，每位分别与left的每位相乘
    for (idx = 1; idx <= L2; ++idx)
    {
        takevoer = 0;
        int rightnum = num2[L2 - idx] - '0';
        //计算每一位与left相乘，left也是从末位循环到首位
        for (j = 1; j <= L1; ++j)
        {
            char resBit = res[Size - j - offset] - '0';
            int num = rightnum * (num1[L1 - j] - '0') + takevoer + resBit;
            takevoer = num / 10;
            res[Size - j - offset] = num % 10 + '0';
        }
        if (takevoer != 0)
            res[Size - j - offset] = takevoer + '0';
        offset++;
    }

    //如果没有进位的话，res最高位没有数字
    if (res[0] == '0')
        res.erase(0, 1);
    return res;
}

int main()
{
    string s1, s2;
    cin >>s1 >> s2;
    string str=Mul(s1,s2);
    cout << str << endl;
}

方法二：优化竖式

乘法竖式还可以这样分解，上图是将num1与num2的每位数相乘后的结果排开来观察，比如num1中的2，从num1的末位向左开始数，位于第1位【注：末位为第0位】，num2的5位于第0位，那么可以观察，他们的结果位于第2位和第1位，如果结果为双位数，则占两位，单位数，占一位。所以结论是num1中的第i位与num2中的第j位，他们的结果占第i+j位和第i+j+1位

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string Mul(string num1, string num2)
{
    size_t L1 = num1.size();
    size_t L2 = num2.size();
    size_t Size = L1 + L2;
    vector<int> resV(Size,0);
    //right从末位循环到首位，每位分别与left的每位相乘
    for (int i = L2-1; i >=0; --i)
    {
        int rightnum = num2[i] - '0';
        //计算每一位与left相乘，left也是从末位循环到首位
        for (int j = L1-1; j >= 0; --j)
        {
            int leftnum = (num1[j] - '0');
            int sum=(resV[i+j+1]+rightnum*leftnum);
            resV[i+j+1]=sum%10;
            resV[i+j]+=sum/10;
        }
    }
    string res;
    for(int i=0;i<resV.size();i++)
    {
        if(i==0&&resV[i]==0)continue;
        res+=resV[i]+'0';
    }
    return res;
}

int main()
{
    string s1, s2;
    cin >>s1 >> s2;
    string str=Mul(s1,s2);
    cout << str << endl;
}

代码中用数组来存当前数的和，最后再转为string
可能有人有所疑问是第21行代码中，resV[i+j]大于10的话是不是会出错，这是不会的，因为for循环中从后到前的，所以最终到24行时，只有可能resV[1]>10，在这个时候resV[0]==0,所以直接将resV跳过即可。处理手段在第27行