高精度减法
高精度减法
高精度核心思想: 模拟手工运算
高精度数据存储: $vector$倒序存储
算法思路
$1.$ 数据存储参考高精度加法
$2.$ 该模板需要保证$A >= B$,所以需要一个$A$ 与 $B$ 的比较。
$(1)$ 如果$A$位数比$B$大,那么$A$大于$B$
$(2)$ $A,B$位数不同,那么就从$A,B$的最高位开始比较,当$A,B$的某一位不同时,返回$A$当前位是否大于$B$
若所有位数均相同,也返回$true$(y总用的是$vector$比较,用$string$会更短些,最后会附带优化)
$3.$ 进行减法时, $t$表示借位,初始化为$0$。每一位开始运算时,$t$加上$A$的本位,$B$存在则减掉$B$。
这时候,$t > 0$就直接放入答案$C$里,$t < 0, t += 10$, 再放入$C$。综合一下就是将$(t + 10) % 10$放入答案
$4.$ $t < 0$则有借位,$t = 1; t > 0$,没有借位,$t = 0$
$5.$ 减完后,有可能存在前导$0$,比如$1111 - 1111$,我们希望得到$0$。
但是没去除前导0时,求出来的是$0000$,所以当答案位数大于$1$时,最高位为$0$就pop_back
代码
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B)// A, B的比较函数
{
if (A.size() != B.size()) return A.size() > B.size();//位数大的数值大
for (int i = A.size() - 1; i >= 0; i -- )//位数相同,从高位向低位比较
if (A[i] != B[i])//当本位的两个数不同时,进行比较,返回大的
return A[i] > B[i];
return true;//两个数完全相等则返回正确,因为判断的是A >= B
}
vector<int> sub(vector<int> &A, vector<int> &B)//加引用是提高效率,引用本质是一个指针
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )//借位为t
{
t = A[i] - t;//被减数当前位减去之前的借位
if (i < B.size()) t -= B[i];//减数本位存在则相减
C.push_back((t + 10) % 10);//放入答案
if (t < 0) t = 1;//更新借位
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导0
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');//数据读入
for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
vector<int> C;
if (cmp(A, B)) C = sub(A, B);//A,B比较, A >= B, A - B, 否则B - A
else C = sub(B, A), cout << '-';
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];//输出答案
cout << endl;
return 0;
}
cmp函数的优化
string 是按照字典序比较的。所以当a, b位数不同返回位数大的,位数相同返回a >= b;
代码如下(已经ac)
bool cmp(string a, string b)
{
if(a.size() != b.size()) return a.size() > b.size();
return a >= b;
}