<=如果觉得有用,别忘记留下一个免费的赞QWQ
高精度算法(High Accuracy Algorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除等运算
$\color{blue}{本页题目传送门:}$791.高精度加法
$\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.再次求赞啦}$
高精度既然用long long都存不下…
$\color{blue}{Q1:如何存储?}$
$\color{Purple}{A1:用数组/向量存}$
将这种大数字拆开,拆成一位一位的,然后用一个数组去表示这个数字
这样这个数字就被称为是高精度数.
当然,为了节(lan)省(de)空(ding)间(yi),我们使用vector存储
注意数组倒序存储
例如,我们存储"5432":
vector <int> vec;//伪代码
vec[0] = 2;
vec[1] = 3;
vec[2] = 4;
vec[3] = 5;
$\color{blue}{Q2:如何输入,输出?}$
$\color{Purple}{A2:重载符号,倒序输入输出}$
定义结构体:
struct bigint {
vector <int> vec;
};
重载输入:
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;
}
$\color{blue}{Q3:如何将两个bigint相加?}$
$\color{Purple}{A3:重载符号+}$
首先重载+=(为了运算方便,特地加上+=):
注意进位!
struct bigint {
vector <int> vec;
bigint& check() {//进位
while(!vec.empty() && !vec.back()) vec.pop_back();
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;
}
};
......
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;}
总结:我们实现了+,+=,cin,cout的大整数功能
最终代码参上:
//
#include <bits/stdc++.h>
using namespace std;
const int N = 10009;
struct bigint {
vector <int> vec;
bigint& check() {
while(!vec.empty() && !vec.back()) vec.pop_back();
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;
}
};
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;
}
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;}
int main() {
bigint x, y;
cin >> x >> y;
cout << x + y << endl;
return 0;
}
制作不易,再次求赞!