高精度算法

大家都知道在c++中不同数据类型都有自己的取值范围

当我们计算特别大的数据时，如果超过了int，甚至是long long的取值范围时，这时就没有合适的变量去运算，这是我们就需要用到高精度算法，顾名思义，高精度算法可以将特别大的数据进行运算，下面我们来看一下

高精度加法

高精度加法的思路和我们刚开始接触加法时的竖式运算一样
$$\begin{array}{r}1234\\ +456\\ 1690\end{array}$$
从个位开始相加，满十进一，加到最高位为止

代码思路：普通数据类型取值范围太小，我们采用数组的方式进行存储。首先定义两个string类s1，s2接受读入的两个数，因为运算时是采用从个位开始运算，所以我们将读入的两个数倒序输入进整形数组a，b中，转化是添加-‘0’将字符类型转换为整形。用一个数组c来记录结果。我们所需要运算的次数就是两个数中位数最多的那个数，定义了len来记录，然后将两个数位数对齐相加，再来一个循环判断是否需要进位，如果大于十就进位，最后将数组c倒序输出即可。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
   
	string s1, s2;
	int a[3000], b[3000], c[3000] = {
   0};
	cin >> s1 >> s2;
	for(int i = 0; i < s1.size(); i++){
   
		a[s1.size() - i - 1] = s1[i] - '0';
	}
	for(int i = 0; i < s2.size(); i++){
   
		b[s2.size() - i - 1] = s2[i] - '0';
	}
	int len = max(s1.size(), s2.size());
	for(int i = 0; i <= len ; i++)
	  c[i] = a[i] + b[i];
	for(int i = 0; i <= len; i++){
   
		if(c[i] >= 10)
		{
   
			c[i + 1] = c[i + 1] + c[i] / 10;
			c[i] = c[i] % 10;  
		}
	}
	if(c[len] != 0)
	  len++;
	for(int i = len - 1; i >= 0; i--)
	  cout << c[i];
	return 0;
 } 
 

高精度减法

高精度减法思路和高精度加法思路大致一样，都是采用竖式计算的思想。

我们知道10-1=9 1-10=-9 两个数一样，当减数和被减数的位置调换后，结果知识正负号改变，在进行减法运算时，我们可以在读入数据时比较一下两个数的大小，始终将大数放在前面进行运算。

代码思路：跟高精度加法类似，先定义数组，然后读入数据。定义一个flag来记录结果符号，读入数据后判断一下s1和s2的大小，始终将大数放在前面。然后逆序读入数组a，b中，因为计算的次数就是最大那个数的位数（s1的位数），然后我们进行运算，每一次运算都判断啊a[i]和b[i]的大小，如果被减数小于减数，被减数借一当十，高位a[i+1]减去1，然后相减的结果存入数组c中。运算后，我们还需要判断一下结果的位数，定义find用来记录，用一个循环找到数组c的位数。最后倒序输出数组c即可。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
   
	string s1, s2;
	int a[30000] = {
   0}, b[30000] = {
   0}, c[30000] = {
   0};
	cin >> s1 >> s2;
	char flag = '+';
	if(s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2))
	{
   
		swap(s1,s2);
		flag = '-';
	}
	for(int i = 0; i < s1.size(); i++)
	  a[s1.size() - i - 1] = s1[i] - '0';
	for(int i = 0; i < s2.size(); i++)
	  b[s2.size() - i - 1] = s2[i] - '0';
	for(int i = 0; i < s1.size(); i++)
	{
   
		if(a[i] < b[i])
		{
   
			a[i] += 10;
			a[i + 1] -= 1;
		}
		c[i] = a[i] - b[i]; 
	}
	if(flag == '-')
	  cout << flag;
	int find = 0;
	for(int i = s1.size() - 1; i >= 0; i--)
	{
   
		if(c[i] != 0)
		{
   
			find = i;
			break;
		}
	}
	for(int i = find; i >= 0; i--)
	  cout << c[i];
	return 0;
}

高精度乘法

高精度乘法运算有着差不多的思想，需要注意的是每次乘积的结果所在的位置，根据下图的公式可以找到规律a[i] * b[i] 对应 c[i + j + 1] 的位置，然后注意一下进位就行。

代码思路：首先读入数字，将数字逆序存入整形数组中，用双重循环进行运算，将a[i] * b[i]得到的结果存入到c[i + j]中，运算对进位处理，遍历整个数组c，如果大于等于10，进位。然后用while循环去掉前导零，最后倒序输出即可

代码实现：

#include<iostream>

using namespace std;

int main()
{
   
	string s1, s2;
	int a[300000], b[300000], c[300000];
	cin >> s1 >> s2;
	int len = s1.size() + s2.size();
	for(int i = 0; i < s1.size(); i++)
	  a[s1.size() - i - 1] = s1[i] - '0';
	for(int i = 0; i < s2.size(); i++)
	  b[s2.size() - i - 1] = s2[i] - '0';	  
	for(int i = 0; i < s1.size(); i++)
	{
   
		for(int j = 0; j < s2.size(); j++)
		{
   
			c[i + j] += a[i] * b[j];
		}
	}
	for(int i = 0; i < len; i++)
	{
   
		if(c[i] >= 10)
		{
   
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
	}
	while(c[len] == 0 && len > 0)
	  len--;
	for(int i = len; i >= 0; i--)
	  cout << c[i];
	return 0;
}

高精度除法

高精度除法用一个大数除一个小数采用逐位试商法

代码思路：跟其他高精度一样，先读入。因为除法运算是从左到右进行的，所以不需要倒序输入进数组中。运算部分每次用大数的第i位除除数，然后利用x每次乘十加上a[i]完成进位。运算后用一个while循环出去前导零，最后输出结果即可。

代码实现：

#include<iostream>

using namespace std;

string s1;
long long b, x, a[5005],c[5005];

int main()
{
   
	cin >> s1 >> b;
	int len = s1.size();
	for(int i = 1; i <= len; i++)
	  a[i] = s1[i - 1] - '0';
	for(int i = 1; i <= len; i++)
	{
   
		c[i] = (x * 10 + a[i]) / b;
		x = (x *10 + a[i]) % b;
	}
	int find = 1;
	while(c[find] == 0 && find < len)
	  find++;
	for(int i = find; i <= len; i++)
	  cout << c[i];
	return 0;
 }