• 基础算法学习|高精度


    高精度

    模板

    高精度加法

    1. // C = A + B, A >= 0, B >= 0
    2. vector<int> add(vector<int> &A, vector<int> &B)
    3. {
    4. //大的数+小的数
    5. if (A.size() < B.size()) return add(B, A);
    6. vector<int> C;
    7. int t = 0;
    8. for (int i = 0; i < A.size(); i ++ )
    9. {
    10. t += A[i];
    11. if (i < B.size()) t += B[i];
    12. C.push_back(t % 10);
    13. t /= 10;
    14. }
    15. //判断最高位是否进位
    16. if (t) C.push_back(t);
    17. return C;
    18. }

    高精度减法

    1. // C = A - B, 满足A >= B, A >= 0, B >= 0
    2. vector<int> sub(vector<int> &A, vector<int> &B)
    3. {
    4. vector<int> C;
    5. for (int i = 0, t = 0; i < A.size(); i ++ )
    6. {
    7. t = A[i] - t;
    8. if (i < B.size()) t -= B[i];
    9. C.push_back((t + 10) % 10);
    10. if (t < 0) t = 1;
    11. else t = 0;
    12. }
    13. //去除前导0
    14. while (C.size() > 1 && C.back() == 0) C.pop_back();
    15. return C;
    16. }

    高精度乘法

    1. // C = A * b, A >= 0, b >= 0
    2. vector<int> mul(vector<int> &A, int b)
    3. {
    4. vector<int> C;
    5. int t = 0;
    6. for (int i = 0; i < A.size() || t; i ++ )
    7. {
    8. if (i < A.size()) t += A[i] * b;
    9. C.push_back(t % 10);
    10. t /= 10;
    11. }
    12. //去除前导0
    13. while (C.size() > 1 && C.back() == 0) C.pop_back();
    14. return C;
    15. }

    高精度除法

    1. // A / b = C ... r, A >= 0, b > 0
    2. vector<int> div(vector<int> &A, int b, int &r)
    3. {
    4. vector<int> C;
    5. r = 0;
    6. for (int i = A.size() - 1; i >= 0; i -- )
    7. {
    8. r = r * 10 + A[i];
    9. C.push_back(r / b);
    10. r %= b;
    11. }
    12. reverse(C.begin(), C.end());
    13. //去除前导0
    14. while (C.size() > 1 && C.back() == 0) C.pop_back();
    15. return C;
    16. }

    例题一

    题目

    给定两个正整数(不含前导 0),计算它们的和。

    输入格式

    共两行,每行包含一个整数。

    输出格式

    共一行,包含所求的和。

    数据范围

    1 ≤ 整数长度 ≤ 100000

    输入样例

    1. 12
    2. 23

    输出样例

    35

    代码示例

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. vector<int> add(vector<int>& A, vector<int>& B) {
    8. if (A.size() < B.size()) return add(B, A);
    9. vector<int> C;
    10. int t = 0;
    11. for (int i = 0; i < A.size(); i++) {
    12. t += A[i];
    13. if (i < B.size()) t += B[i];
    14. C.push_back(t % 10);
    15. t /= 10;
    16. }
    17. if (t) C.push_back(t);
    18. return C;
    19. }
    20. int main() {
    21. string a, b;
    22. cin >> a >> b;
    23. vector<int> A, B;
    24. for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    25. for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    26. auto C = add(A, B);
    27. for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    28. cout << endl;
    29. return 0;
    30. }

    例题二

    题目

    给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。

    输入格式

    共两行,每行包含一个整数。

    输出格式

    共一行,包含所求的差。

    数据范围

    1 ≤ 整数长度 ≤ 100000

    输入样例

    1. 32
    2. 11

    输出样例

    21
    

    代码示例

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. bool cmp(vector<int>& A, vector<int>& B) {
    8. if (A.size() != B.size()) return A.size() > B.size();
    9. for (int i = A.size() - 1; i >= 0; i--)
    10. if (A[i] != B[i]) return A[i] > B[i];
    11. return true;
    12. }
    13. vector<int> sub(vector<int>& A, vector<int>& B) {
    14. vector<int> C;
    15. int t = 0;
    16. for (int i = 0; i < A.size(); i++) {
    17. t = A[i] - t;
    18. if (i < B.size()) t -= B[i];
    19. C.push_back((t + 10) % 10);
    20. if (t < 0) t = 1;
    21. else t = 0;
    22. }
    23. //去前导0
    24. while (C.size() > 1 && C.back() == 0) C.pop_back();
    25. return C;
    26. }
    27. int main() {
    28. string a, b;
    29. cin >> a >> b;
    30. vector<int> A, B;
    31. for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    32. for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    33. if (cmp(A, B))
    34. {
    35. auto C = sub(A, B);
    36. for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    37. }
    38. else
    39. {
    40. auto C = sub(B, A);
    41. cout << "-";
    42. for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    43. }
    44. cout << endl;
    45. return 0;
    46. }

    例题三

    题目

    给定两个非负整数(不含前导 0) A 和 B,请你计算 A * B 的值。

    输入格式

    共两行,第一行包含整数 A,第二行包含整数 B

    输出格式

    共一行,包含 A * B 的值。

    数据范围

    1 ≤ A的长度 ≤100000,

    0 ≤ B ≤10000

    输入样例

    1. 2
    2. 3

    输出样例

    6

    代码示例

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. vector<int> mul(vector<int>& A, int b) {
    8. vector<int> C;
    9. int t = 0;
    10. for (int i = 0; i < A.size() || t; i++) {
    11. if (i < A.size())t += A[i] * b;
    12. C.push_back(t % 10);
    13. t /= 10;
    14. }
    15. //去前导0
    16. while (C.size() > 1 && C.back() == 0) C.pop_back();
    17. return C;
    18. }
    19. int main() {
    20. string a;
    21. int b;
    22. cin >> a >> b;
    23. vector<int> A;
    24. for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    25. auto B = mul(A, b);
    26. for (int i = B.size() - 1; i >= 0; i--) cout << B[i];
    27. cout << endl;
    28. return 0;
    29. }

    例题四

    题目

    给定两个非负整数(不含前导 0) AB,请你计算 A / B 的商和余数。

    输入格式

    共两行,第一行包含整数 A,第二行包含整数 B

    输出格式

    共两行,第一行输出所求的商,第二行输出所求余数。

    数据范围

    1 ≤ A的长度 ≤100000,

    0 ≤ B ≤10000,

    B一定不为0

    输入样例

    1. 7
    2. 2

    输出样例

    1. 3
    2. 1

    代码示例

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7. vector<int> div(vector<int>& A, int b, int& r) {
    8. vector<int> C;
    9. r = 0;
    10. for (int i = A.size() - 1; i >= 0; i--) {
    11. r = r * 10 + A[i];
    12. C.push_back(r / b);
    13. r %= b;
    14. }
    15. reverse(C.begin(), C.end());
    16. while (C.size() > 1 && C.back() == 0) C.pop_back();
    17. return C;
    18. }
    19. int main() {
    20. string a;
    21. int b, r;
    22. cin >> a >> b;
    23. vector<int> A;
    24. for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    25. auto B = div(A, b, r);
    26. for (int i = B.size() - 1; i >= 0; i--) cout << B[i];
    27. cout << endl << r << endl;
    28. return 0;
    29. }

  • 相关阅读:
    2022年8月22日上午七点CKA考试界面改动exe软件答题
    JAVA开发(Redis的使用, redis数据类型)
    GFS分布式文件系统
    SpringCloud (三) ——Nacos注册中心
    开发语言工具编程系统化教程入门和初级专辑课程上线
    IOS 16 RC升级 IOS 16 步骤
    k8s--基础--23.7--认证-授权-准入控制--限制用户操作k8s资源的权限
    【小程序源码】二维码DIY背景美化生成器
    Windows与网络基础-15-本地安全策略
    uniapp书写顶部选项卡代码详细例子
  • 原文地址:https://blog.csdn.net/2203_75720729/article/details/133930970