算法基础 1.4 高精度 （加减乘除）

高精度加法模版：
计算 C = A +B，这里默认低位在前面，例如num=123在A中的存在形式是[3,2,1]。

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

高精度减法模版：
使用的时候用cmp判断下A是否大于等于B，如果返回真就算sub（A,B），否则算sub（B,A）最后记得加负号。

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();  //去除前导0 
	return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22