高精度算法详解-CSDN博客

本文链接：https://blog.csdn.net/Wonderful_Day4z/article/details/81062267

暑假开始啦！然而某市四中某s老师给他的学生下达了任务：在暑假结束前，要在某知名评测网站上AC 100题

在s老师的学生中有一位w同学看了看自己的刷题量

愤怒的他开始刷水题，直到他看见了一道喜闻乐见的A+B problem（出自洛谷P1601）

他一看，哇！金色！传说！这种题还用想吗？上代码

结果自然是

经过20分钟+的挣扎，w同学终于放弃了，来找同为蒟蒻但是却会一些高精度的g同学帮忙

他再一看，数据范围（a,b<=10^500）就蒙了

且不说这个同学不看题的毛病

我们来讨论一下，为什么会WA

Q：你觉得电脑存储的数字大小有极限吗？

如果你觉得没有，那你就大错特错了

上面的例子就是一个鲜明的写照

在c++中，如果使用int型存储，其最大限制约为-2^31~2^31-1（约有10位数）

如果使用long long int型存储，其最大限制约为-2^63~2^63-1(约有19位数）

而超过这个大小的数，会输出奇奇怪怪的内容（以下为用上面的代码打出的结果）

而高精度算法，就是来解决这一切的（我来！）

使用高精度，可以存上千万位数的大数！

什么？你说你的一个数要有上亿位？~~你见过有人把数组开上亿的吗，那都是新手才干的。~~

你赢了，但是在比赛中，绝对不会出现这样的数~~（虽然高精度也很难会出）（出这种题的人会被全国OIer骂的）~~

Part 1 高精度的输入与存储

//part 1 高精度的存储方法
//<1>由于高精度的特殊性，我们采用string字符串格式存储高精度整数
//<2>也可采用循环加数组的方法进行存储,不能直接输入数字，要作为字符输入，之后转换为数字 
//tip<1>:string格式不能使用scanf("%s")输入，只能使用cin输入，之后将其存入数组中，利用数组进行计算 
//tip<2>:string格式的首位是从0开始,但利用length求长度时会比此多一位 
//tip<3>:在方法2中，由于最后一位是空格或回车，故真正的数组长度为length-1 
#include<bits/stdc++.h>
using namespace std;
int a[12000];
char k[12000];
void init1()
{
	string s;
	cin>>s;//tip<1> 
	a[0]=s.length();
	for(int i=1;i<=a[0];++i)
	{
		a[i]=s[i-1]-48;//tip<2> 
	}
	for(int i=1;i<=a[0];++i)
	{
		printf("%d",a[i]);
	}
}
void init2()
{
	int length=0;
	for(int i=1;;++i)
	{
		scanf("%c",&k[i]);
		if(k[i]==' '||k[i]=='\n')
		{
			length=i;//tip<3> 
			break;
		}
	}
	for(int i=1;i<length;++i)
	{
		a[i]=k[i]-48;
	}
	for(int i=1;i<length;++i)
	{
		printf("%d",a[i]);
	}
} 
int main(){
	init1();//<1> 
	init2();//<2>
}

Part 2 高精度的加法

在高精度算法中，大多数都是按照竖式方式解，如果无法理解可以对照代码自己模拟理解

//part 2 高精度加法
//<1>同时存储两个数组，这个代码使用的是上面代码中的方法<1> 
//<2>a数组存储被加数,b数组存储加数,c数组存储结果 
//tip<1>:一定注意s,m,a,b,c数组的起始位置,s及m作为字符串数组,其起始位置为0.a,b,c数组作为存储数的数组,其起始位置为1
//tip<2>:清楚两数相加时的进位过程 
//tip<3>:在两数相加时,我们的位数(lenc)是从1往上增,这是我们采取倒序输出并且处理最高进位的原因 
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000],c[10000],lena,lenb,lenc,x；
string s,m;
int main()
{
    cin>>s>>m;
    lena=s.length();
    lenb=m.length();
    for(int i=0;i<=lena-1;++i)a[lena-i]=s[i]-48;
    for(int i=0;i<=lenb-1;++i)b[lenb-i]=m[i]-48;
	lenc=1;x=0;
    while(lenc<=lena||lenc<=lenb)
    {
        c[lenc]=a[lenc]+b[lenc]+x;//x可以看做一个进位标记，在下一位才使用 
        x=c[lenc]/10;//这也是为什么先处理x再++lenc 
        c[lenc]%=10;
        ++lenc;//位数变化 
    }
    c[lenc]=x;
    if(c[lenc]==0)--lenc;//处理最高进位 
    for(int i=lenc;i>=1;--i)printf("%d",c[i]);//倒序输出 
    return 0;
}

看到这里，w同学松了一口气，看来他终于可以把那道坑人的A+B problem 给AC掉了，喜加一。

可他没想到，还有更多的题向他涌来

乐于助人的g同学决定帮人帮到底，接下来，我们帮他把这一个专题过完！

Part 3 高精度减法

//part 3 高精度减法 
//<1>和加法的思路相似,但需要注意的是，被减数必须比减数大 
//<2>处理进位和处理借位有所不同，但还是很相似 
//tip<1>:当被减数小于减数时，高精度算法不再适用，所以要交换被减数和减数，并输出负号 
//tip<2>:string字符串并没有有效的比较大小方式(至少g同学不知道)，所以转换为字符数组进行判断 
//tip<3>:在循环减数的过程中，由于不知道lena与lenb哪个大，所以只要lenc满足小于等于其中一个，就继续循环 
#include<bits/stdc++.h>
using namespace std;
int a[100000],b[100000],c[100000],lena,lenb,lenc,x;
char n[100000],n1[100000],n2[100000];
string s,m;
int main()
{
    cin>>s>>m;
    lena=s.length();
    lenb=m.length();
    for(int i=0;i<=lena-1;++i)n1[i]=s[i];//tip<2>
    for(int i=0;i<=lenb-1;++i)n2[i]=m[i];
    if(strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))//tip<1> 
    {
    	strcpy(n,n1);
    	strcpy(n1,n2);
    	strcpy(n2,n);
    	printf("-");
	}
	lena=strlen(n1);lenb=strlen(n2);
	for(int i=0;i<=lena-1;++i)a[lena-i]=n1[i]-48;
    for(int i=0;i<=lenb-1;++i)b[lenb-i]=n2[i]-48;
	lenc=1;x=0;
	int x=1;
    while(x<=lena||x<=lenb)//tip<3>
    {
    	if(a[x]<b[x])//借位过程 
    	{
    		a[x]+=10;
    		--a[x+1];
	}
	c[x]=a[x]-b[x];//相减过程 
	++x;
	}
    lenc=x;
    while((c[lenc]==0)&&(lenc>1))--lenc;
    for(int i=lenc;i>=1;--i)printf("%d",c[i]);
    return 0;
}

Part 4 高精度乘法

//part 4 高精度乘法 
//<1>依旧使用竖式，但在乘法中有特殊的规律 
//<2>根据列竖式分析c数组的下标规律，有c[i+j-1]=a[i]*b[i]+x+c[i+j-1],x为进位标记 
//tip<1>:依旧要考虑删除前导的0 
//tip<2>:c的位数就是a的位数+b的位数（可能会有前导0），由乘法的规律可得 
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000],c[10000],lena,lenb,lenc,x;
string s,m;
int main()
{
    cin>>s>>m;
    lena=s.length();
    lenb=m.length();
    for(int i=0;i<=lena-1;++i)a[lena-i]=s[i]-48;
    for(int i=0;i<=lenb-1;++i)b[lenb-i]=m[i]-48;
    for(int i=1;i<=lena;++i)
    {
    	x=0;
    	for(int j=1;j<=lenb;++j)
    	{
    		c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
    		x=c[i+j-1]/10;
    		c[i+j-1]%=10;
		}
		c[i+lenb]=x;
	}
    lenc=lena+lenb;//tip<2>
    while(c[lenc]==0&&lenc>1)--lenc;//tip<1>
    for(int i=lenc;i>=1;--i)printf("%d",c[i]);
    return 0;
}

Part 5 高精度除法（低精）

//part 5 高精度除法（低精） 
//<1>在高精度除法中，要涉及到乘法运算和减法运算，以及移位处理，此处采取按位相除法 
//tip<1>:和高精度乘法一样，由于c的最终位数可能会变化，所以有一个删除前导0的过程 
//tip<2>:移位过程中x的算法有所不同
#include<bits/stdc++.h>
using namespace std;
int a[10000],b,c[10000],lena,lenc,x;
string s;
int main()
{
    cin>>s;
    scanf("%d",&b);
    lena=s.length();
    for(int i=0;i<=lena-1;++i)a[i+1]=s[i]-48;
    for(int i=1;i<=lena;++i)
    {
    	c[i]=(x*10+a[i])/b;
    	x=(x*10+a[i])%b;
	}
    lenc=1;
    while(c[lenc]==0&&lenc<lena)++lenc;//删除前导的0 
    for(int i=lenc;i<=lena;++i)printf("%d",c[i]);
    return 0;
}

暂时解决了这么多问题，w同学受益匪浅，毕竟高精度是一个比较冷门的专题