acwing算法基础课笔记3

发表于 更新于 分类于 Artalk： loading...

前言

高精度加法、减法、乘法和除法

简概

image-20211012190508715

两个大整数A和B（a）加/减/乘/除，一般A是大数（len(A) ≤10610^6），a稍小（a≤10000）

大整数的存储

一般是将大整数的每一位存到数组里去，而且为了后续计算方便，是逆序存储，即低位在前。如下图所示：

image-20211012191158811

原因：如果最高位产生进位，直接在数组末尾添加进位的1，实现比较简单，无须数组元素的移动。

高精度加法

acwing 793. 高精度加法

简概

先从最低位开始，每位的数字相加，超过10则向相邻高位进1.

image-20211012191719913

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C = A + B
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;
    }
    // 最高位如果产生进位，则在末尾补1
    if (t == 1) C.push_back(1);
    return C;
}

高精度减法

acwing 794. 高精度减法

简概

image-20211012194328583

从最低位开始，每位数字相减，不够减就借位

计算前先判断，如果A≥B，则计算A-B

如果A≤B，则计算B-A，然后加负号，跟人类计算减法思路一致。

算法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>

using namespace std;
// 判断两个大整数谁大 
// 是否有 A>=B
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;
}

// 假定两个正整数且 A≥B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); ++i) {
        t = A[i] - t;
        // 判断B是否存在相应位
        if (i < B.size()) t -= B[i];
        // 学习下面的处理方式
        C.push_back((t + 10) % 10);
        // t<0 需要借位
        if (t < 0) t = 1;
        else t = 0;
    }
    
    // 减法有个问题：要去除前导0
    // 例如 321 - 320 = 001 去掉前面两个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;
    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];
    cout << endl;

    return 0;
}

高精度乘法

acwing793. 高精度乘法

简概

image-20211013152417776

这里预设A是个大整数，B是个小一点的整数，1≤A的长度≤100000, 0≤B≤10000

因此做乘法的时候，循环A的每一位，将之与B相乘。

PS： 若A与B均为大整数，则双重循环。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> mul(vector<int> &A, int B) {
    vector<int> C;
    int t = 0;
    // 处理方法跟高精度加法类似，但有区别
    // 最后的进位
    for (int k = 0; k < A.size() || t != 0; ++k) {
        if (k < A.size()) t += A[k] * B;
        C.push_back(t % 10);
        t /= 10;
    }
    // 去除前导0
    // 例如 1234 * 0 = 0 而不是0000
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度除法

acwing 794. 高精度除法

简概

image-20211013160844377

同加减乘类似，每次相除，用余数r暂时保存本次相除的被除数，等于高一位的余数x10加上本位的数

算法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C = 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 = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    // 反转一下C 保持低位在前
    reverse(C.begin(), C.end());
    // 去除前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}