大数乘法-526互联

洛谷P1009的大数阶乘和促使我学会了大数阶乘以及大数加法，连夜赶忙看了下大数乘法的思路就顺便写了一下

大数乘法的思路也和加法相似，都是模拟竖式运算，这里我们开大数组，用数组的每一位模拟大数字的每一位数

然后定义两个数组First和Last来存储要运算的两个大数，Answer数组来存储运算的结果

相对于加法的实时处理进位不同，对于乘法我们所做的是先将每一位先算出，最后统一考虑进位的顺延问题

代码如下

#include<stdio.h>
#include<string.h>
typedef int Len;
Len Get_Num(int* Num)
{
    int k = 0;
    char Temp[1000];
    scanf("%s", Temp);
    int len = strlen(Temp)-1;
    for (int i=len; i >= 0; i--)
        Num[k++]=Temp[i] - '0';
    return len;
}
int main()
{
    int First[1000] = { 0 };
    int Last[1000] = { 0 };
    int Answer[1000] = { 0 };
    int LofFirst=Get_Num(First);//Len of First
    int LofLast=Get_Num(Last);//Len of Last
    //计算First乘以Last
    for (int k=0;k<=LofLast;k++)
    {
        for (int i = 0; i <= LofFirst; i++)
        {
            int Temp = First[i] * Last[k];
            Answer[i+k]+= Temp;
        }
    }
    int LastNot0= 999;
    while (!Answer[LastNot0])
        LastNot0--;//滤掉0，找到前缀中不为0的第一个元素的下标，
//下面进行进位的顺延处理
    int Num = 0;//进位指标
    for (int p = 0; p <= LastNot0; p++)
    {
        int Temp = Answer[p] + Num;//临时存储
        Answer[p] = Temp % 10;//取出个位
        Num = Temp / 10;//取出十位，当然也可能是百位等，或者说取出去掉个位的数
    }
    while (Num)//当num还有剩余时，单独进行处理
    {
        Answer[++LastNot0] = Num % 10;//++LastNot0，即向前再进一位
        Num /= 10;//更新
    }
    for (;LastNot0 >= 0; LastNot0--)
        printf("%d", Answer[LastNot0]);//逆序输出
    return 0;
}

需要说明的是对于存储结果的数组Answer的操作

由我们列竖式时的操作可知，每次乘以乘数的一位数，相加时是会向更高一位错一位的

这里的下标是Answer的下标，可以看到，First[i]*Last[j]后的结果，是要存储到Anwser[i+j]的位置上的，

也就是说，作为First的乘数乘以作为Last的乘数的得数，要写在比First的下标i的位置错位Last的下标i位置的位置上，即i+j上