高精度算法:加减乘除 (学习笔记)
加法：
现有vector<int>a,b;并且已经输入了内容且倒置
vector<int> plus(vector<int>a,vector<int> b){
int as = a.size();
int bs = b.size();
vector<int>total;
int carry = 0;
int ar = 0, br = 0; //读取位数
while (ar < as && br < bs) {
int tmp = a[ar++] + b[br++]+carry;
if (tmp >= 10) {
carry = 1; //判断进位
tmp = tmp % 10;
}
else {
carry = 0; //没有进位需要记住去置空
}
total.emplace_back(tmp);
}
while (ar < as) {
int tmp = a[ar++] + carry;
if (tmp >= 10) {
carry = 1;
tmp %= 10;
}
else carry = 0;
total.emplace_back(tmp);
}
while (br < bs) {
int tmp = b[br++] + carry;
if (tmp >= 10) {
carry = 1;
tmp %= 10;
}
else carry = 0;
total.emplace_back(tmp);
}
if (carry == 1)total.emplace_back(carry);
return total; //记得回去倒置
}
可以判断长度后进行优雅的处理(假设a的长度大于等于b的)
For(int i=0,t=0;i<a.size();i++){
t+=a[i];
If(i<b.size())t+=b[i];
Total.emplace_back(t%10);
If(t>=10)t=1;
Else t=0;
}
这样的处理就更加的优雅了
减法：
如果是两个整数的减法，需要确定一下两个数的大小，也就是我们需要再来一个cmp的函数来比较a和b的大小
Cmp：
int cmp(vector<int> a, vector<int> b) {
if (a.size() > b.size())return 1;//a更长一定更大
else if (a.size() < b.size()) {
return 0;//b更长，b更大
}
else{ //位数一样，从最高位开始比较，知道出现一个不一样的数，返回大的
for (int i = a.size() - 1; i >= 0;i--) {
if (a[i] != b[i])return a[i] > b[i];
}
}
return 1; //一样的就返回1
}
减法的具体的函数：（也是优雅的！！）
vector<int> sub(vector<int> a,vector<int> b){//a,b记得倒置
int as = a.size(); //默认a更大,我们可以在函数外进行比较后放入这个函数
vector<int>total;
int t = 0;
for (int i = 0; i < as; i++) {
t = a[i] - t;
if (i < b.size())t -= b[i];
total.emplace_back((t + 10) % 10); //+10防止出现负数
if (t >= 0)t = 0;
else t = 1;
}
while (total.size() > 1 && total.back() == 0)total.pop_back();
return total;//记得倒置
}
一大乘以一小的乘法：
和加法一样，没有多大的区别，有的话就是carry的大小的最后carry的处理
直接上代码：
vector<int> time(vector<int> a,int b){
int as = a.size(); //记得倒置
int t = 0;
vector<int> total;
for (int i = 0; i < as; i++) {
t += a[i] * b;
total.emplace_back(t % 10);
t /= 10;
}
while (t) {
total.emplace_back(t % 10);
t /= 10;
}
return total;//记得倒置
}
一大除一小的除法：
只是需要涉及到的有3个翻转，具体的操作和大横线除法一样，从最高位开始计算，依次先
余数乘以10加上现在位的数除以b得到当前位置的答案，余数为当前余数求b的余数，最后一次翻转加上去掉后缀的0
具体的代码在下面：
vector<int> div(vector<int> a,int b){ //这里的a不用倒置,但是为了统一口径,就都倒置下
reverse(a.begin(),a.end()); //复原下
vector<int> res;
r = 0;
for (int i = a.size() - 1; i >= 0; i--) {
r = r * 10 + a[i];
res.emplace_back(r / b);
r %= b;
}
reverse(res.begin(),res.end());
while (res.size() > 1 && res.back() == 0)res.pop_back();
return res; //记得倒置再输出结果
}