📟作者主页：慢热的陕西人
🌴专栏链接：C++算法
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
主要讲解了高精度算法的四种常用的计算
Ⅲ. 高精度
以下数字均指位数
①A + B（精度均在10^6）
②A - B （精度均在10^6）
③A * b (len(A) <= 10^6, a <= 1000);
④A / b (len(A) <= 10^6, a <= 1000);
Ⅲ. Ⅰ . A + B：
思路：将两个大数先用字符串保存，然后再倒序存入到数组中（这是因为我们在运算的时候会产生进位）。然后再实现一个add函数实现加法，将运算的结果存储到一个数组中：
代码：
#include <iostream> #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) C.push_back(1); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; //将A和B存储在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'); auto C = add(A, B); for (int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]); return 0; }
Ⅲ. Ⅱ . A - B：
思路：存储思路都是统一的，需要一个借位t.
每一位的计算：
x = Ai - Bi - t,如果x大于零那么本位减法的结果就是x,如果x小于零那么需要在x结果的基础上加上10总结果的计算：如果
A >= B那么结果就是A - B，如果A < b那么结果就是-(B - A)在计算之前我们要保证每次都是大数减小数，所以要先实现一个
cmp函数来比较哪一个数字大。代码：
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int>& A, vector<int>& 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; } 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; } //去除前导零 while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; //将A和B存储在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'); if (cmp(A, B)) { auto C = sub(A, B); for (int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]); } else { auto C = sub(B, A); printf("-"); for (int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]); } return 0; }
Ⅲ. Ⅲ. A * b：
思路：存储数据的思路不变，特别的点在于对进位和本位计算的处理。
例如：我们要计算123 * 12。
首先我们将
3 * 12 + t存到t里面，那么本位就是t % 10 = 6, 而进位就是t / 10 = 3;以此类推将
2 * 12 + t存到t里面，那么本位就是t % 10 = 7，而进位就是t / 10 = 2;最后我们将
1 * 12 + t存到t里面，那么本位就是t % 10 = 4, 而进位就是t / 10 = 1最后如果
t不为零的话，那么最高位的值就是继续将t进行分解。代码：
#include <iostream> #include <vector> using namespace std; vector<int> mul(vector<int>& A,int b) { vector <int> C; for (int i = 0, t = 0; t || i < A.size(); ++i) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } return C; } int main() { string a; int b; vector<int> A; cin >> a >> b; //将A和B存储在a和b的字符串中 for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]); return 0; }
Ⅲ. Ⅲ. A / b:
思路：A / B 的话我们是从高位开始计算的，而且计算机每次只能计算一位。
那么我们每次计算都将余数存储在
r中，然后每次都将r * 10，最后再加上除数的本位，然后再次计算余数，直到除数计算完成。代码：
#include <iostream> #include <vector> using namespace std; //A 是除数， b是被除数，r是余数 vector<int> div(vector<int>& A,int b, int &r) { vector <int> 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; } int main() { string a; int b; int r = 0; vector<int> A; cin >> a >> b; //将A和B存储在a和b的字符串中 for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0'); auto C = div(A, b, r); for (int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]); cout << endl << r; return 0; }
到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话，可以点赞，收藏，顺便关注一下！
如果文章内容有错误，欢迎在评论区指正
