<=如果觉得有用,别忘记留下一个免费的赞QWQ
高精度算法(High Accuracy Algorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除等运算
$\color{blue}{本页题目传送门:}$ 793.高精度乘法
$\color{blue}{拓展题目传送门:}$ 114.国王游戏
$\color{blue}{上一次分享:}$ 一段代码实现所有高精度四则运算!(减法篇)
$\color{Purple}{持续更新中…}$
为什么要用高精度?
$\color{blue}{在c++中,int, long long等存储方式只能计算十几位的整数运算}$
$\color{blue}{而当我们想要计算更多位时,就需要用到高精度}$
$\color{Purple}{前排提醒:}$
$\color{Purple}{1.本分享采用c++语言}$
$\color{Purple}{2.最终会将所有代码运算整合,更方便使用!}$
$\color{Purple}{3.本页代码仅针对无符号整数}$
$\color{Purple}{4.再次求赞啦!}$
乘除法操作更为复杂…
在int(long long)中,我们相乘都使用*符号!(废话)
而我们的高精度运算则是模拟手算的方法
举个乘法的例子
计算114 * 514:
我们用竖式来理解
114
*514
---------
首先计算4 * 4 = 16
接着计算1(十位) * 4 = 4
再计算1(百位) * 4 = 4
所以114 * 4 = 256
...(以此类推)
所以:
$\color{blue}{Q1:如何计算两个bigint相乘的结果}$
$\color{Purple}{A1:遍历vector,分别将两个大整数的每一位都做乘法,最终将乘积相加}$
由于加法具有交换律,我们就按照从低到高的顺序来进行计算
$\color{blue}{Q2:有注意事项吗?}$
$\color{Purple}{A2:特别注意进位}$
检查进位操作,我们还是用check来实现!
首先是 * 操作的实现:
bigint operator * (const bigint &a,const bigint &b) {
bigint n;
n.vec.assign(a.vec.size() + b.vec.size() - 1, 0);
for(int i = 0; i != a.vec.size(); ++ i)
for(int j = 0; j != b.vec.size(); ++ j)
n.vec[i + j] += a.vec[i] * b.vec[j];
return n.check();
}
顺便重定义 *= 符号:
//一定要写在 * 的后面
bigint& operator *= (bigint &a, const bigint &b) {
return a = a * b;
}
本章总结:我们实现了, =的大整数功能!
最终代码参上:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10009;
struct bigint {
//bool flag = true;
vector <int> vec;
bool operator != (const bigint &e) const{
if(vec.size() != e.vec.size()) return true;
for(int i = vec.size() - 1;i >= 0;-- i)
if(e.vec[i] != vec[i]) return true;
return false;
}
bool operator == (const bigint &e) const{
if(vec.size() != e.vec.size()) return false;
for(int i = vec.size() - 1;i >= 0;-- i)
if(e.vec[i] != vec[i]) return false;
return true;
}
bool operator < (const bigint &e) const{
if(vec.size() != e.vec.size()) return vec.size() < e.vec.size();
for(int i = vec.size() - 1;i >= 0;-- i)
if(vec[i] != e.vec[i]) return vec[i] < e.vec[i];
return false;
}
bool operator > (const bigint &e) const{
if(vec.size() != e.vec.size()) return vec.size() > e.vec.size();
for(int i = vec.size() - 1;i >= 0;-- i)
if(vec[i] != e.vec[i]) return vec[i] > e.vec[i];
return false;
}
bigint& check() {//在各类运算中经常用到的进位小函数,不妨内置
while(!vec.empty() && !vec.back()) vec.pop_back();//去除最高位可能存在的0
if(vec.empty()) return *this;
for(int i = 1;i < vec.size();++ i) {
vec[i] += vec[i - 1] / 10;
vec[i - 1] %= 10;
}
while(vec.back() >= 10) {
int e = vec.back();
vec.back() %= 10;
vec.push_back(e / 10);
}
return *this;//为使用方便,将进位后的自身返回引用
}
}x, y;
istream &operator >>(istream &is, bigint &e) {
string s;
is >> s;
e.vec.clear();
for(int i = s.size() - 1;i >= 0;-- i) e.vec.push_back(s[i] - '0');
return is;
}
ostream &operator <<(ostream &os, const bigint &e) {
if(e.vec.empty()) os << 0;
for(int i = e.vec.size() - 1; i >= 0; -- i) os << e.vec[i];
return os;
}
bool operator <= (const bigint &e,const bigint &e1) {return !(e > e1);}
bool operator >= (const bigint &e,const bigint &e1) {return !(e < e1);}
bigint& operator += (bigint &e, const bigint &e1) {
if(e.vec.size() < e1.vec.size()) e.vec.resize(e1.vec.size());
for(int i = 0;i != e1.vec.size();++ i) e.vec[i] += e1.vec[i];
return e.check();
}
bigint operator + (bigint e, const bigint &e1) {return e += e1;}
bigint& operator -= (bigint &e, bigint e1) {
if(e < e1) swap(e, e1);
for(int i = 0; i != e1.vec.size(); e.vec[i] -= e1.vec[i], ++ i)
if(e.vec[i] < e1.vec[i]) {
int j = i + 1;
while(!e.vec[j]) ++ j;
while(j > i) {-- e.vec[j]; e.vec[-- j] += 10;}
}
return e.check();
}
bigint operator - (bigint e, const bigint &e1) {return e -= e1;}
bigint operator * (const bigint &a,const bigint &b) {
bigint n;
n.vec.assign(a.vec.size() + b.vec.size() - 1, 0);
for(int i = 0; i != a.vec.size(); ++ i)
for(int j = 0; j != b.vec.size(); ++ j)
n.vec[i + j] += a.vec[i] * b.vec[j];
return n.check();
}
bigint& operator *= (bigint &a, const bigint &b) {
return a = a * b;
}
int main() {
cin >> x >> y;
cout << x * y << endl;
return 0;
}
制作不易,再次求赞!