文章目录
前言
一、高精度运算概述
二、高精度算法
1. 高精度加法
AcWing791. 高精度加法
高精度加法模板
AC代码
2.高精度减法
AcWing 792. 高精度减法
高精度减法模板
AC代码
3.高精度乘法
AcWing 793. 高精度乘法
高精度乘法模板
AC代码
4.高精度除法
AcWing 794. 高精度除法
高精度除法模板
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：高精度运算，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上
一、高精度运算概述
我们都知道，我们定义一个数，不论是整数还是浮点数，它都是有范围的都是有限的，就拿unsigned long long为例，它的最大值也就1e19，意思是最多只有19位，而我们想要进行40位，50位甚至更多位数的运算，显然就不能简单的定义int，long long等类型进行计算了，这时候我们就可以运用到高精度算法，把每一位上的数都存到数组之中，本博客的高精度算法中，用到了STL中的vector，关于vector，详见：vector
二、高精度算法
1. 高精度加法
AcWing791. 高精度加法
本题链接：AcWing791. 高精度加法
本博客给出题目截图：
高精度加法模板
本模板来自ACWing算法基础课
vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); //保证A的长度始终 ≥ B的长度，因为下面的for循环是通过遍历A的每个元素 vector<int> C; //C中存储的就是A + B后的结果 int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); //有可能最高位加法存在进位，如果t存在，就加入到C return C; } vector<int> add(vector<int> &A, vector<int> &B) { if (A.size() < B.size()) return add(B, A); //保证A的长度始终 ≥ B的长度，因为下面的for循环是通过遍历A的每个元素 vector<int> C; //C中存储的就是A + B后的结果 int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); //有可能最高位加法存在进位，如果t存在，就加入到C return C; }
AC代码
#include <iostream> #include <cstring> #include <vector> using namespace std; vector <int> A, B, C; void add(vector <int> &A, vector <int> &B) { if (A.size() < B.size()) add (B, A); int t = 0; for (int i = 0; i < A.size(); i ++ ) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); } int main() { string a, b; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); //a[i] - '0'，就把char类型的数字变成了int类型的a[i] for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); add(A, B); for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]); return 0; }
2.高精度减法
AcWing 792. 高精度减法
本题链接：AcWing 792. 高精度减法
本博客给出题目截图：
高精度减法模板
本模板来自ACWing算法基础课
// C = A - B, 满足A >= B, A >= 0, B >= 0 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); //因为t可能是负的 //举个例子，我们计算10 - 8，对于个位而言就是-8，我们通过(t + 10) % 10的方法就可以得到2 if (t < 0) t = 1; //证明存在借位，即像高位借1 else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导0 //比如111111118 - 111111117 = 000000001，而我们要输出1，通过这一步骤可以实现，要求C.size() > 1是因为有可能答案就是0 return C; }
AC代码
保证始终是绝对值大的数去减绝对值小的数：
#include <iostream> #include <cstring> #include <vector> using namespace std; vector <int> A, B, C; bool cmp(vector <int> &A, vector <int> &B) //比较A和B谁大 { if (A.size() != B.size()) return A.size() > B.size(); else { for (int i = A.size() - 1; i >= 0; i -- ) if (A[i] != B[i]) return A[i] > B[i]; } return true; } void sub(vector <int> &A, vector <int> &B) { int t = 0; for (int i = 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(); } int main() { string 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'); if (cmp(A, B)) sub (A, B); else { sub (B, A); printf("-"); } for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; return 0; }
3.高精度乘法
AcWing 793. 高精度乘法
本题链接：AcWing 793. 高精度乘法
本博客给出题目截图：
高精度乘法模板
本模板来自ACWing算法基础课
vector<int> mul(vector<int> &A, int b) { vector<int> C; int t = 0; for (int i = 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 //比如 123 * 0，按照这个运算的话是 0000，答案是0，故需要去除前导0 return C; }
AC代码
#include <iostream> #include <vector> #include <cstring> using namespace std; vector <int> A, B; void mul(vector <int> &A, int b) { int t = 0; for (int i = 0; i < A.size() || t; i ++ ) { t += A[i] * b; B.push_back(t % 10); t /= 10; } while (B.size() > 1 && B.back() == 0) B.pop_back(); } int main() { string a; int b; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); mul(A, b); for (int i = B.size() - 1; i >= 0; i -- ) cout << B[i]; return 0; }
4.高精度除法
AcWing 794. 高精度除法
本题链接：AcWing 794. 高精度除法
本博客给出本题截图：
高精度除法模板
本模板来自ACWing算法基础课
vector<int> div(vector<int> &A, int b, int &r) //传入的是r的地址，所以可以直接对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()); //除法和加法，减法，乘法运算都不一样的是除法运算是高位向低位进行，而其他三种运算是从低位到高位运算 //所以除法运算的前导0其实是在开头而不是尾部，而我们只能从尾部删除一个元素，所以我们要把C翻转 while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导0 return C; }
AC代码
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; vector <int> A, C; int r; void div(vector <int> A, int b) { 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(); } int main() { string a; int b; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); div(A, b); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl << r; return 0; }
三、时间复杂度
关于高精度算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
