题目如下:
描述:
求两个不超过200位的非负整数的积。
输入:
有两行,每行是一个不超过200位的非负整数,没有多余的前导0。
输出:
一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。
样例输入:
12345678900
98765432100
样例输出:
1219326311126352690000
思路:
这个题主要是考虑如果数据大于电脑所能储存的范围该如何计算,这就可以回归我们如何手算两数相乘了
可以将数据先以字符串的形式储存到数组中,然后再转换为整型进行计算。
当然我们的核心思路就是如下:
乘法原理:
乘法竖式
1 2 3
* 4 5
——————————————
6 1 5
+ 4 9 2
——————————————
5 5 3 5
1.核心代码(乘法运算部分)是由模拟乘法竖式算出来的,我们要知道:
(1) 数1的倒数第i位与数2的倒数第j位相乘所得到的值应存在结果的倒数第i+j位上。
(2) 如果结果的i+j位大于9,则进位到i+j+1位。
num[i+j]+=big1[i]*big2[j];
num[i+j+1]+=num[i+j]/10;
num[i+j]%=10;
- 要注意考虑乘积为零的时候
for(i=m+n-1;i>=1;i--)//除去末尾后的零,这里i>=1就是考虑了乘积为0
{
if(num[i]==0)//遇到0就删除,最多删到只剩一个0,就是结果为0的时候
k--;
else
break;
}
- 要知道一个i位和一个j位的数相乘,得到的结果不会超过i+j位
源码如下:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
char a[200];
char b[200];
int big1[200]={0};
int big2[200]={0};
int num[2000]={0};
int m,n;
int i,j,k;
cin>>a;
m=strlen(a);//获得输入字符串的长度
cin>>b;
n=strlen(b);
for(i=0;i<m;i++)//将字符转换为数再倒序输入
{
big1[m-1-i]=a[i]-'0';
}
for(i=0;i<n;i++)
{
big2[n-1-i]=b[i]-'0';
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
num[i+j]+=big1[i]*big2[j];
num[i+j+1]+=num[i+j]/10;
num[i+j]%=10;
}
}
k=m+n;//结果长度
for(i=m+n-1;i>=1;i--)//除去末尾后的零
{
if(num[i]==0)
k--;
else
break;
}
for(i=k-1;i>=0;i--)//倒序输出
{
cout<<num[i];
}
}