Section 4.高精度

一、高精度加法（正数+正数）

大整数的存储：将个位存在 $a[0]$ ，十位存在 $a[1]$ ，百位存在 $a[2]$ ......，方便进位，因为如果按照正序存储的话，最高位需要进位时，所有数字都需要向右移一位
模拟竖式加法

vector::size()函数的用法：假设有vector<>a，则a.size()返回数组a的长度

vector::push_back()函数的用法：函数将一个新的元素加到vector<>的最后面，位置为当前最后一个元素的下一个元素，参数为要插入的值

#include <iostream>
#include <vector>
using namespace std;
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);  //如果加完后仍有进位，则加一位最高位1
	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');  //把数字逆序存放
	auto C = add(A, B);
	for (int i = C.size() - 1; i >= 0; i--)
		printf("%d", C[i]);  //再逆序输出
	return 0;
}

二、高精度减法（正数-正数）

大整数的存储：同上
模拟竖式减法：同位相减如果小于0，则再加上10，后一位减去1
注意考虑结果可能为负数：如果 $a-b \gt 0$ ，直接计算就行；如果 $a-b \lt 0$ ，则先计算 $b-a$ ，再加负号

vector::back()函数的用法：访问vector<>中的最后一个元素

vector::pop_back()函数的用法：取消vector<>中最后一个元素的地址映射。效果：使用.size()时会忽略该元素，但是如果使用指针，会发现该元素仍然存在，说明该函数没有真正把内存里面的数值删掉

#include <iostream>
#include <vector>
using namespace std;
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;
	}
}
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;
		if (i < B.size())
			t -= B[i];  //因为B的位数一定小于等于A，所以要考虑i超过了B的最高位时的情况
		C.push_back((t + 10) % 10);  //同时考虑了需要借位与不需要借位时的情况
		if (t < 0)
			t = 1;  //向前借位
		else
			t = 0;
	}
	while (C.size() > 1 && C.back() == 0)  //去除前导0，但是结果为0的时候不能把最后一个0也去掉，所以以位数来判断是否结果为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');  //把数字逆序存放
	if (cmp(A, B))  //A>B
	{
		auto C = sub(A, B);
		for (int i = C.size() - 1; i >= 0; i--)
			printf("%d", C[i]);  //再逆序输出
	}
	else  //A<B
	{
		auto C = sub(B, A);
		cout << "-";  //先输出负号
		for (int i = C.size() - 1; i >= 0; i--)
			printf("%d", C[i]);  //再逆序输出
	}
	return 0;
}

三、高精度乘法（高精度*低精度）

大整数的存储：同上
模拟竖式乘法：将高精度上的每一位数乘以整个低精度数（和小学竖式乘法略有不同），该位就为结果模10，进位就为结果除10

#include <iostream>
#include <vector>
using namespace std;
vector<int>mul(vector<int>A, int b)
{
	vector<int>C;
	int t = 0;  //进位标记
	for (int i = 0; i < A.size() || t; i++)  //“或t”是考虑到最后一位也可能有进位
	{
		if (i < A.size())  //最后一位进位时直接跳过此步
			t += A[i] * b;
		C.push_back(t % 10);  //当前位
		t /= 10;  //进位
	}
	while (C.size() > 1 && C.back() == 0)  //去除前导0，但是结果为0的时候不能把最后一个0也去掉，所以以位数来判断是否结果为0
		C.pop_back();
	return C;
}
int main()
{
	string a;
	int b;
	cin >> a >> b;
	vector<int>A;
	for (int i = a.size() - 1; i >= 0; i--)
		A.push_back(a[i] - '0');  //倒序存储
	auto C = mul(A ,b);
	for (int i = C.size() - 1; i >= 0; i--)
		printf("%d", C[i]);  //倒过来输出
	return 0;
}

四、高精度除法（高精度除低精度）

大整数的存储：同上
模拟竖式除法：递归

reverse(first,last)函数的用法：该函数在头文件<algorithm>中，作用是反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），该函数没有返回值。

vector::begin()函数的用法：该函数返回一个指向vector的第一个元素的迭代器

vector::end()函数的用法：该函数返回一个指向vector的past-the-end元素的迭代器，它不指向最后一个元素，因此要获取我们可以使用的最后一个元素，应该用vector::end()-1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>div(vector<int>A, int b, int& r)  //通过引用传回r
{
	vector<int>C;
	r = 0;
	for (int i = A.size() - 1; i >= 0; i--)
	{
		r = r * 10 + A[i];  //这一位的最终被除数等于上一位的余数乘10加上这一位的被除数
		C.push_back(r / b);
		r %= b;
	}
	reverse(C.begin(), C.end());
	while (C.size() > 1 && C.back() == 0)  //去前导0
		C.pop_back();
	return C;
}
int main()
{
	string a;
	int b;
	cin >> a >> b;
	vector<int>A;
	for (int i = a.size() - 1; i >= 0; i--)
		A.push_back(a[i] - '0');  //逆序存储
	int r;  //余数
	auto C = div(A, b, r);
	for (int i = C.size() - 1; i >= 0; i--)
		printf("%d", C[i]);  //逆序输出
	cout << endl << r << endl;  //输出余数
	return 0;
}

五、配套练习