高精度加法 (大整数相加)
算法思路
低位在前, 高位在后, 以向量存储每一位, 按位进行加法
- vector add(vector &A, vector &B) {
- vector 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) {
- C.push_back(1);
- }
- return C;
- }
高精度减法 (大整数相减)
算法思路
类似于加法, 按位来计算
- vector sub(vector &A, vector &B) {
- vector c;
- int t = 0;
- for (int i = 0; i <A.size(); i ++ ) {
- t = A[i] - t;
- if (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();
- }
- return c;
- }
高精度乘法 (大数乘以一个小数)
算法思路
直接每一位进行乘法, 每次乘法之后将高位放入向量中.
- vector mul(vector &A, int b) {
- vector c;
- int t = 0;
- for (int i = 0; i <A.size() || t; i ++ ) {
- if (A.size()) {
- t += A[i] * b;
- }
- c.push_back(t % 10);
- t /= 10;
- }
- return c;
- }
高精度除法 (大数除以小数)
算法思路
反向计算每一位的除法, 获取最低位的值, 最后进行翻转即可
- vector div(vector &A, int b, int &r) {
- vector c;
- r = 0;
- 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;
- }
来源: http://www.bubuko.com/infodetail-3122774.html