|
发表于 2020-3-7 15:16:19
来自手机
|
显示全部楼层
本帖最后由 rtems 于 2020-3-7 15:19 编辑
大数乘法?看看我儿子写的公众号上的一篇。
https://mp.weixin.qq.com/s?__biz ... rg%2FgJt95AVcTEaJBC
算法2: 高精度乘法
何长青 智子笔记 2月19日
题目描述:给出两个整数(a、b),计算它们的积。
输入:一行两个整数(1 < a,b < 10^1000)
输出:一行一个整数,表示a*b
因为上限还是1000位,所以照样还是高精度。。。
一样,乘法也需要手写竖式,但是与加法不同的是,乘法需要将第二个数的每一位都乘一遍第一个数。
是不是很懵。。。
没事,一步一步来
我们平时算乘法时要列的竖式长这个样子:
5 5
x 5 5
——————
2 7 5
2 7 5
——————
3 0 2 5
分解一下(以下文字需要很深的思考,需要读者慢慢阅读、思考)
第一步,把第一个55的每一位都乘以第二个55的个位,也就是5,得到积275。
第二步,把第一个55的每一位都乘以第二个55的十位,也就是5,得到积275。(实际上这个275代表着2750)
第三步,将275与2750相加,得到答案3025
是不是还是很懵。。。
继续拆解第一步
首先,我们将第一个55的个位5乘以第二个55的个位5,得到25,存在答案的个位,进位给答案的十位,很正常对吧
其次,我们将第一个55的十位5乘以第二个55的个位5,得到25,存在答案的十位,进位给答案的百位
我们发现在乘法中,第二个55的个位5乘的不是5,而是50,也就是5 * 5 *(10^1)。得到的应该是250
继续找规律,第二步
首先,我们将第一个55的个位5乘以第二个55的十位5,得到25,存在答案的十位,进位给答案的百位
这里,第一个55的个位5乘的不是5,而是50,也就是5 * 5 *(10^1)。得到的应该是250
其次,我们将第一个55的十位5乘以第二个55的十位5,得到25,存在答案的百位,进位给答案的千位
这里,第二个55的十位5乘的不是5,而是50;第一个55的十位乘的也不是5,而是50,也就是5 * 5 * (10^2),得到的是2500
这时,规律已经找出了
我们不妨把个位设为0位,十位设为1位,百位设为2位,以此类推。。。
每一次相乘,得到的结果(25)都存在答案的 位数 + 位数 位。
用编程语言表示:ans[i+j] += a[j] * b (i和j分别表示第二个数的位数和第一个数的位数)
其余的需要注意点就是,需要在最后处理的时候去掉首位的0。
在处理进位的时候,要注意乘法中的进位可能不止19,所以不是一个简单的-10就可以搞定的。。。
#include <iostream>
#include <cstring>
using namespace std;
#define MAXLEN 1005
#define MAXLEN2 1000005
string la, lb; // 用字符串输入两个数
int a[MAXLEN], b[MAXLEN], ans[MAXLEN2]; // a是第一个数,b是第二个数, ans是积(这里长度要单独处理,以免RE)
int len; // 积的长度
void MULTIPLICATION()
{
for (int i = 0; i < la.length(); i++)
{
for (int j = 0; j < lb.length(); j++)
{
ans[i+j] += (a * b[j]); // 将第一个数的第i位与第二个数的第j位的积存到ans的i+j位
if (ans[i+j] >= 10) // 处理进位
{
ans[i+j+1] += (ans[i+j] / 10);
ans[i+j] %= 10;
}
}
}
}
int main()
{
cin >> la >> lb; // 输入
memset(ans, 0, MAXLEN); // 将ans的每一位初始化为零
for (int i = 0; i < la.length(); i++) a[la.length()-i-1] = la - '0'; // 倒着输入第一个数
for (int i = 0; i < lb.length(); i++) b[lb.length()-i-1] = lb - '0'; // 倒着输入第二个数
len = la.length() + lb.length(); // 将积的长度暂定为两个数的长度之和
MULTIPLICATION(); // 乘法
while (ans[len-1] == 0) len--; // 去除最高位的0
for (int i = len - 1; i >= 0; i--) cout << ans; // 输出
return 0;
}
|
|