初音ミクの消失

大整数乘法题解

字数统计: 883阅读时长: 3 min
2018/12/06 Share

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<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

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

原文作者:mrh929

原文链接:https://mrh1s.top/posts/80036358/

发表日期:December 6th 2018, 11:39:02 pm

更新日期:May 4th 2019, 11:39:44 pm

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG