【c++】算法：高精度（经典加减乘除）{含解析（图解）}

Hi~?o(*￣▽￣*)ブ，今天来一起看看c++算法之高精度

之后会持续更新有关c++算法系列，欢迎观看！(#^.^#)

目录

前言

使用高精度的目的：

基本方法介绍：?

?一、A+B?problem

基本思路解析：

具体步骤：

代码如下：

二、A-B problem

基本思路解析：

?编辑

具体步骤:

?代码如下：

?三、A*B problem

基本思路解析：

具体步骤（多一步去零）?

代码如下：

?四、A/B problem

基本思路解析：

具体步骤（多一步去零）?

?代码如下：

总结

---

前言

使用高精度的目的：

简单来说，当一个数足够大时，甚至超过longlong范围，这个时候我们就可以用上高精度算法，对这些数进行加减乘除操作了

基本方法介绍：?

该算法最主要的就是数组了，我们把大数看作字符再存入数组中，再用数组记录结果，最后用数组输出，同时因为加减乘除运算的独特性，还会对数组进行逆序输出，排序等一系列操作

?

?一、A+B?problem

基本思路解析：

补充说明对a,b数组的操作 ：

对a、b数组的详细操作

a[100000]	由于是从个位加起，所以我们会将对a数组的录入反过来，例如这里会有a[1]=8,a[2]=8,a[3]=1(从1开始还是从0开始都可以）
b[10000]	由于是从个位加起，所以我会将对b数组的录入反过来，例如里面会有b[1=8,b[2]=8,b[3]=1(从1开始还是从0开始都可以）

具体步骤：

1.字符串读入

string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
	cin>>x>>y;
	la=x.length();
	lb=y.length();

2.字符串转数组

这里解释一下，因为加法是从个位开始的，所以我们让字符串的最后一位存到数组的第一个去

for(int i=0;i<la;i++)
	{
		a[la-i]=x[i]-'0';
	}
	for(int i=0;i<lb;i++)
		{
			b[lb-i]=y[i]-'0';
		}

3.竖式加法?

 lc=max(la,lb);//找到两数间的最大值，最大的那个是结果的长度（或者是结果长度-1）
	for(int i=1;i<=lc;i++)
	{
		c[i]+=a[i]+b[i];//注意这里的+=，这里+的是两个数和前面进位的
		c[i+1]=c[i]/10;//往前进一位
		c[i]%=10;//进位后剩下的
	}	

4.倒序输出
?

if(c[lc+1]>0)lc++;//最高位仍然进位，所以长度++
	for(int i=lc;i>=1;i--)//逆序输出
	cout<<c[i];

代码如下：

#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
	cin>>x>>y;
	la=x.length();
	lb=y.length();
	for(int i=0;i<la;i++)//将大数转化为一个个数字并且存入数组中顺便进行逆存
	{
		a[la-i]=x[i]-'0';
	}
	for(int i=0;i<lb;i++)//同上
		{
			b[lb-i]=y[i]-'0';
		}
    lc=max(la,lb);//找到两数间的最大值，最大的那个是结果的长度（或者是结果长度-1）
	for(int i=1;i<=lc;i++)
	{
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;
	}	
	if(c[lc+1]>0)lc++;//最高位仍然进位，所以长度++
	for(int i=lc;i>=1;i--)//逆序输出
	cout<<c[i];
	return 0;
}

二、A-B problem

基本思路解析：

具体步骤:

1.字符串读入

string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
	cin>>x>>y;
	la=x.length();
	lb=y.length();

?2.字符串转数组

和之前一样，因为减法是从个位开始的，所以我们让字符串的最后一位存到数组的第一个去

for(int i=0;i<la;i++)
	{
		a[la-i]=x[i]-'0';
	}
	for(int i=0;i<lb;i++)
		{
			b[lb-i]=y[i]-'0';
		}

3.竖式减法?

   for(int i=1;i<=la;i++)
	{
		if(a[i]<b[i])//减数小了 
		{
			a[i]+=10;//往前借位 
			a[i+1]-=1;//前一位减一 
		}
	c[i]=a[i]-b[i];//照常计算 
	}

4.倒序输出

	for(int i=la;i>=1;i--)
	{
		cout<<c[i];
	}

?代码如下：

#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[100000],b[100000],c[100000],la,lb;
int main()
{
	cin>>x>>y;
	la=x.size();
	lb=y.size();
	if(la<lb||la==lb&&x<y)
	{
		swap(la,lb);
		swap(x,y);
	cout<<'-';
	}
	for(int i=0;i<la;i++)
	{
		a[la-i]=x[i]-'0';
	}
		for(int i=0;i<lb;i++)
		{
			b[lb-i]=y[i]-'0';
		}
    for(int i=1;i<=la;i++)
	{
		if(a[i]<b[i])//减数小了 
		{
			a[i]+=10;//往前借位 
			a[i+1]-=1;//前一位减一 
		}
	c[i]=a[i]-b[i];//照常计算 
	}

	for(int i=la;i>=1;i--)
	{
		cout<<c[i];
	}
	return 0;
}

?

?三、A*B problem

基本思路解析：

具体步骤（多一步去零）?

1.字符串读入

string x,y;
int a[1000000],b[1000000],c[1000000],la,lb,lc;
int main()
{
	cin>>x>>y;
	la=x.length();
	lb=y.length();

?2.字符串转数组

和之前一样，因为乘法也是从个位开始的，所以我们让字符串的最后一位存到数组的第一个去

for(int i=0;i<la;i++)
	{
		a[la-i]=x[i]-'0';
	}
	for(int i=0;i<lb;i++)
		{
			b[lb-i]=y[i]-'0';
		}

3.竖式乘法

for(int i=1;i<=la;i++)
		{
			for(int j=1;j<=lb;j++)
			{
				c[i+j-1]+=a[i]*b[j];//正常相除，c[i]中结果的位数可以通过观察总结 
				c[i+j]+=c[i+j-1]/10;//向前进位 
				c[i+j-1]%=10;//进位剩下的 
			}
		}

4.去零

去零指在特殊情况中如003*25=0075需要去除结果需要去除结果中的零

lc=la+lb;//两数相乘的最大位数 
		while(c[lc]==0&&lc>1)lc--; 

5.倒序输出

?
	for(int i=la;i>=1;i--)
	{
		cout<<c[i];
	}

?

代码如下：

#include <bits/stdc++.h>
using namespace std;
string x,y;
int a[100000],b[100000],c[100000],la,lb,lc;
int main()
{
	cin>>x>>y;
	la=x.size();
	lb=y.size();
	for(int i=0;i<la;i++)
	{
		a[la-i]=x[i]-'0';
	}
	for(int i=0;i<lb;i++)
		{
			b[lb-i]=y[i]-'0';
		}
		for(int i=1;i<=la;i++)
		{
			for(int j=1;j<=lb;j++)
			{
				c[i+j-1]+=a[i]*b[j];//正常相除，c[i]中结果的位数可以通过观察总结 
				c[i+j]+=c[i+j-1]/10;//向前进位 
				c[i+j-1]%=10;//进位剩下的 
			}
		}
		lc=la+lb;//两数相乘的最大位数 
		while(c[lc]==0&&lc>1)lc--; 
	for(int i=lc;i>=1;i--)
	{
		cout<<c[i];
	}
	return 0;
}

?四、A/B problem

基本思路解析：

?

具体步骤（多一步去零）?

1.字符串读入

string a1;
long x=0,la,lc,a[100000],c[100000],b1;
int main()
{
	cin>>a1>>b1;
	la=a1.size();

?2.字符串转数组

和之前不同，因为除法是从最高位开始的，所以我们让字符串的第一位存到数组的第一个去

	for(int i=0;i<la;i++)
	{
		a[i]=a1[i-1]-'0';
	}

?3.除法

for(int i=1;i<=la;i++)
{
	c[i]=(x*10+a[i])/b1;//除不尽的*10再加上下一位 
	x=(x*10+a[i])%b1;//除不尽剩下的 
}
lc=1;

4.去零

while(c[lc]==0&&la>lc)lc++;

5.直接输出

这里不用逆序

for(int i=lc;i<=la;i++)
{
	cout<<c[i];
}

?代码如下：

#include <bits/stdc++.h>
using namespace std;
string a1;
long x=0,la,lc,a[100000],c[100000],b1;
int main()
{
	cin>>a1>>b1;
	la=a1.size();
	for(int i=0;i<la;i++)
	{
		a[i]=a1[i-1]-'0';
	}
for(int i=1;i<=la;i++)
{
	c[i]=(x*10+a[i])/b1;//除不尽的*10再加上下一位 
	x=(x*10+a[i])%b1;//除不尽剩下的 
}
lc=1;
while(c[lc]==0&&la>lc)lc++;
for(int i=lc;i<=la;i++)
{
	cout<<c[i];
}
return 0;
}

总结

①前面的字符串读入和字符串转换加减乘是一样的

②去零操作存在于减乘除中

③注意+=和=的区别

④谢谢大家耐心看完，希望能帮助到您！！(#^.^#)