一、算法描述
高精度加减法讨论的是两个大整数之间的运算。
而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。
算法思路:
-
还是模拟小学的乘法列竖式,只不过此时不太一样,原本的列竖式是一位一位的乘,这里需要改变一下思路。
-
这里直接把小整数当成一个数,所乘的数直接当成进位参与运算即可。
-
每次进位
t += A[i] * b
,然后将当前位数上的数(t % 10
)加入答案数组,然后让t
成为下一位的进位,t /= 10
。 -
因为是乘法,所以会有可能超过很多位,我们需要把他们都加入答案数组而且不要忘了一位一位的加。
-
如果一个很大的数乘 \(0\) 的话,那么会产生很多前导 \(0\) ,我们也需要处理一下。
经过优化之后代码如下:
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); ++i)
{
t += b * A[i];
C.push_back(t % 10);
t /= 10;
}
while (t) C.push_back(t % 10), t /= 10;
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
二、题目描述
给定两个非负整数(不含前导 \(0\)) \(A\) 和 \(B\),请你计算 \(A×B\) 的值。
输入格式
共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)。
输出格式
共一行,包含 \(A × B\) 的值。文章来源:https://www.toymoban.com/news/detail-710943.html
数据范围
\(1≤A的长度≤100000,\)
\(0≤B≤10000\)文章来源地址https://www.toymoban.com/news/detail-710943.html
输入样例:
2
3
输出样例:
6
三、题目来源
四、源代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); ++i)
{
t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (t) C.push_back(t % 10), t /= 10;
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
vector<int> C = mul(A, b);
for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
return 0;
}
到了这里,关于高精度乘法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!