[数据结构与算法]【学习报告】高精度算法

写在前面

?? 你曾经是不是有过这样的经历：好不容易用了暴力的方法写出了代码，测试用例也通过了，当心满意足的提交代码后却弹出一个超出”数据范围“的提示，整个人瞬间😱了？我是经常有这样的经历，终于在既懒得优化不会优化又忍受不了的情况下，我发现了高精度算法。

一、简介高精度算法

1.什么是高精度算法

高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。

以上内容来自高精度算法_360百科

2.高精度算法的应用范围

高精度算法的应用范围说广也广，说不广也不广。他不想排序那样能够运用到搜索、贪心甚至数据结构方面，而且在一定程度上高精度算法过于繁琐（大部分题目的数据long long及以下就可以解决）。
但是对于某些热衷于暴力求解的童鞋（比如我）来说，在遇到某些需要暴力+优化的题目时，可以不考虑优化，直接运用高精度算法来求解。😌

二、高精度算法的实现

1.高精度算法之加法

高精度加法是利用数组来模拟加法
先举个例子：194+256

??????194

+ ???256
————
??????650

从以上表格中可以看到加法是同时进行的，而进位必须从低位到高位来实现。而在代码实现中可以加法和进位同时进行，以提高效率。

代码实现

#include<stdio.h>
#include<string.h> 
#define MAXN 1000//首先宏定义来用于数组大小
int a[MAXN],b[MAXN],c[MAXN];//定义用来存储数据的数组a,b以及计算的数组c。
int main(){
char s[MAXN],ss[MAXN];//定义字符串数组来储存数字a,b
scanf("%s%s",s,ss);
int sta=strlen(s),stb=strlen(ss);//确定加法执行后结果最小位数 
int len=sta>stb?sta:stb;
for(int i=sta-1,j=0;i>=0;i--,j++)a[j]=s[i]-'0';//为了便于处理，把数字反向输入数组
for(int i=stb-1,j=0;i>=0;i--,j++)b[j]=ss[i]-'0';
for(int i=0;i<len;i++){//i从以开始， 
	c[i]+=a[i]+b[i];//模拟加法，因为可能含有进位，所以是+= 
	c[i+1]=c[i]/10;//模拟进位
	c[i]%=10;//若进位，保留进位后结果 
} 
if(c[len]){//若存在进位，则长度加一，确保最后输出正确
	len++;
} 
for(int i=len-1;i>=0;i--){
	printf("%d",c[i]);
}
return 0;
}

2.高精度算法之乘法

同理，高精度乘法也是利用数组来模拟两数相乘

?? ???????194
x ???????256
—————
????????1164
????????970
??????388
??????49664

乘法的整个过程体现在表格中，观察表格，可以发现第i+j-1格（代码化）上是由数字一[i] * 数字二[j]，可以一起先全部加起来再进位，提高效率。

#include<stdio.h>
#include<string.h> 
#define MAXN 10000//首先宏定义来用于数组大小
int a[MAXN],b[MAXN],c[MAXN];//定义用来存储数据的数组a,b以及计算的数组c,因为拆分的时候直接累加，所以只需一维数组即可 
int main(){
char s[MAXN],ss[MAXN];//定义字符串数组来储存数字a,b
scanf("%s%s",s,ss);
int sta=strlen(s),stb=strlen(ss);
for(int i=sta-1;i>=0;i--)a[sta-i]=s[i]-'0';//为了便于处理，把数字反向输入数组
for(int i=stb-1;i>=0;i--)b[stb-i]=ss[i]-'0';//因为是乘法，所以位数限制与乘法类似
for(int i=1;i<=sta;i++){
	for(int j=1;j<=stb;j++){
		c[i+j-1]+=a[i]*b[j];//直接累加 
	}
} 
int len=sta+stb;//因为999x999=998001（仅仅举个例子）,所以乘积位数不会超过 两个乘数位数之和。 
for(int i=1;i<=len;i++){
	c[i+1]+=c[i]/10;//模拟进位
	c[i]%=10;//若进位，保留进位后结果 
} 
while(!c[len]){//处理前面多余的零，确定真是位数 
	len--;
}
for(int i=len>1?len:1;i>=1;i--){//防止结果为零不输出 
	printf("%d",c[i]);
}
return 0;
}

以上代码部分借鉴于洛谷（本人技术有限😭）

三、总结

高精度算法对于暴力来说还是有一定应用范围的，特别是头疼于时间复杂度与空间复杂度时，高精度计算可以避免陷入第三次头疼。

这是本人第一次写博客，如有喜欢，望好评🙂