大整数乘法题解

mrh929

6 年前

09:大整数乘法

总时间限制:

1000ms

内存限制:

65536kB

描述

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

输入

有两行，每行是一个不超过200位的非负整数，没有多余的前导0。

输出

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

样例输入

12345678900

98765432100

样例输出

1219326311126352690000

来源

程序设计实习2007

题解：

这道题的参数过大，甚至不能用长整型变量解决，那么就应该使用高精度算法。我们曾经写过高精度加法，本题算法只是高精度加法的延伸。

将两个数用字符串数组读入，再转化成整型数组储存，此时储存顺序应该为倒序，即第一位用来存放个位，第二位存放十位，以此类推……（这样的目的是在于它能方便我们进位时的数据存放），好了这里有一个问题，题目并没有提到输入数据中不是先序0（如00003、0000等），所以这里可以添加判断语句只截取有意义的部分（当然也可以在计算之后判断再最高位的数字，如果为0则不输出）

接下来是整个算法的核心部分！！我们知道，高精度加法是对应位相加，如果结果大于等于10则进一位，然而乘法只是加法的一个高级形式而已，所以我们也可以将此高精度乘法转化为多个高精度加法，即a数中的每一位数去乘b数中的每一位数，最后求和。

经过观察，我们可以发现，当我们将某x位的数乘某y位的数时，两个数除了最高位之外其余位都为0，运算结果为两数之积，而它所在的位数为x+y，用两个for循环，就可以实现a数中的每一位数去乘b数中的每一位数。而得到的结果则ans[x+y]+=两数之积，这样就得到了未进位的两大数相乘的结果（源码中我使用了进位，实际上可以删除）。

最后一步，进位操作。从最低位算起

ans[i+1]=ans[i]/10;

ans[i]%=10;

输出。AC！！喜悦！！

#include
#include
#include
#include

int a[300],b[300],ans[1000];
int work(int n,bool t)//n输入的字符（数字） t是否转换成数字 
{//字符与数字的转换函数 
    if(t==1)
        return n-'0';
    else
        return '0'+n;
}

int main()
{
    char c[300];
    int len_a,len_b;
    gets(c);
    len_a=strlen(c);
    for(int i=len_a;i>=1;i--)
        a[len_a-i]=work(c[i-1],1);//以倒序整型读入两个数
    gets(c);
    len_b=strlen(c); 
    for(int i=len_b;i>=1;i--)
        b[len_b-i]=work(c[i-1],1);
    
    int ji;   //对两个数进行操作，但不进位，保存在ans[]中 
    for(int i=0;i<=len_a-1;i++)
        for(int j=0;j<=len_b-1;j++)
        {
            ji=a[i]*b[j];
            ans[i+j+1]+=ji/10;
            ans[i+j]+=ji%10;//此处累赘，可以不用进位，到最后一同进位 
        }
    
    int j=0,log;
    while(j<=len_a+len_b-2)//进位操作 
    {
        log=ans[j];
        if(log>=10)
        {
            ans[j]=log%10;
            ans[j+1]+=log/10;
        }
        j++;
    }
    /*if(ans[len_a+len_b-2]==0)
        j--;*/
    while(ans[j]==0&&j>=0)
        j--;
    if(j==-1)
        j++;
    for(int i=j;i>=0;i--)//输出数字
        printf("%c",work(ans[i],0));
    
    return 0;
}