高精度加法
主要思路就是利用编程模拟人工的加法
方便操作使用vector来存储这些数
为了方便进位，需要将原数字倒过来存储到vector中
加完所有位之后别忘了判断最后一位的进位
最后需要将vector中的数倒着输出
#include<iostream> #include<string> #include<vector> using namespace std; vector<int> add(vector<int>& A, vector<int>& B){ vector<int> C; int t = 0; for(int i = 0; i < A.size() || i < B.size(); i++){ if(i < A.size()) t += A[i]; if(i < B.size()) t += B[i]; C.push_back(t%10); t /= 10; } if(t > 0) C.push_back(t); 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'); //倒着将数存入vector for(int i = b.size()-1; i >= 0; i--) B.push_back(b[i]-'0'); auto C = add(A, B); //倒着输出 for(int i = C.size()-1; i >= 0; i--){ cout << C[i]; } return 0; }
高精度减法
存储方式与高精度加法一样
在减操作前，先判断a,b的大小，都转换成大数-小数的形式，如果结果是负数，先输出一个负号
对于每一位的操作，都是：减数-被减数-借位
每次需要判断被减数是否有对应的这一位，没有就用0代替
借位初始化为0，在每次操作后，如果得到的是负数，借位就是1，否则就是0
每一位的得数有两种情况，t<0, t>=0
如果t>0得数就是t，否则得数是t+10
最后倒着输出结果即可
#include<iostream> #include<vector> #include<string> using namespace std; //A >= B bool cmp(vector<int> &A, vector<int> &B){ if(A.size() < B.size()) return false; else if(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; } vector<int> sub(vector<int> &A, vector<int> &B){ vector<int> C; for(int i = 0, t = 0; i < A.size(); i++){ 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; } //去除前导0 注意留1位 while(C.size() > 1 && C.back() == 0) C.pop_back(); 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); else C = sub(B, A), cout << "-"; for(int i = C.size()-1; i >= 0; i--) cout << C[i]; return 0; }
高精度乘法
存储方式和前面一样，只是这里的相乘方式和手算的方式不一样
这里需要将乘数的每一位分别与被乘数相乘加上这一位的进位
每一位的相乘结果为t，则t%10为得数的相应位的数，t/10为进位的数
#include<iostream> #include<string> #include<vector> using namespace std; vector<int> mul(vector<int> &A, int b){ vector<int> C; for(int i = 0, t = 0; i < A.size() || t; i++){ if(i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while(C.size() > 1 && C.back() == 0) C.pop_back(); //如果全是乘0，所有位数都是0 return C; } int main(){ string a; int b; cin >> a; cin >> 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]; cout << endl; return 0; }
高精度除法
除法与前面的几种高精度运算都不太一样的地方在于
数据的存储方式，这里需要从除数的最高位开始运算，所以得到的数字也是从高位开始的
这里只需要将运算完的vector去除前导0之后reverse一下即可
做除法运算时，首先需要将上次除法得到的余数*10+下一位数字作为除数
然后除数/被除数得到商
除数%被除数得到这次运算的余数
最后的余数就是整个除法运算的余数
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; vector<int> div(vector<int> &A, int b, int &r){ vector<int> C; for(int i = A.size()-1; i >= 0; i--){ r = r*10 + A[i]; C.push_back(r/b); r %= b; } reverse(C.begin(), C.end()); while(C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main(){ string a; int b; cin >> a; cin >> b; vector<int> A; for(int i = a.size()-1; i >= 0; i--) A.push_back(a[i]-'0'); int r = 0; vector<int> C = div(A, b, r); for(int i = C.size() - 1; i >= 0; i--) cout << C[i]; cout << endl << r << endl; return 0; }
