初音未来の消失

大整数乘法题解

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;
}

退出移动版