高精度(二)：vector实现

前置知识

vector，函数，模拟

目标

用函数实现高精度加、减、乘、除

高精度数字仍然采用倒序存储。

去掉前导零

void clear(vector<int> &A) {
    while (A.size() > 1 && A.back() == 0)
        A.pop_back();
}

比较大小

int cmp(vector<int> A, vector<int> B) {
    if (A.size() != B.size())
        return A.size() > B.size() ? 1 : -1;

    for (int i = A.size() - 1; i >= 0; i--)
        if (A[i] != B[i])
            return A[i] > B[i] ? 1 : -1;

    return 0;
}

高精加高精

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(t);

    return C;
}

高精减高精

要求 A >= B。

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;
    }

    clear(C);

    return C;
}

高精乘低精

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;
    }

    clear(C);

    return C;
}

高精乘高精

vector<int> mul(vector<int> A, vector<int> B) {
    vector<int> C(A.size() + B.size() + 1);

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    for (int i = 0; i + 1 < C.size(); i++) {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    clear(C);

    return C;
}

高精除低精

计算：

A / b = C …… r

vector<int> div(vector<int> A, int b, int &r) {
    vector<int> C(A.size());

    r = 0;

    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];

        C[i] = r / b;
        r %= b;
    }

    clear(C);

    return C;
}

高精除高精

vector<int> div(vector<int> A, vector<int> B) {
    vector<int> C(A.size());
    vector<int> R(1, 0);

    for (int i = A.size() - 1; i >= 0; i--) {
        R.insert(R.begin(), A[i]);
        clear(R);

        while (cmp(R, B) >= 0) {
            R = sub(R, B);
            C[i]++;
        }
    }

    clear(C);

    return C;
}

总结

vector版本重点：

• 不需要手动维护长度
• 运算写成独立函数
• 高精除高精需要比较和减法