C++基础算法教程——高精度算法

欢迎来到沾花把玖的C++算法课堂!

高精度算法

利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。

高精度计算中需要处理好以下几个问题:

1.数据的接受方法和存贮方法

当输入的数很长时,可采用字符串的方式读入,这样可以输入位数很长的数,利用字符串函数和操作运算,将每一位数取出,存入数组中。

void init(int a[]){     //传入一个数组
	string s;
	cin>>s;     //读入字符串s
	int len=s.length();     //用len计算字符串s的位数 
	for(int i=1;i<len;i++)
	    a[i]=s[len-1]-'0';     //将字符串s转换为数组a,并倒序存储 
}

另一种方法是直接用循环加数组的方法输入数据。

2.高精度位数的确定

接收时往往是用字符串的,所以它的位数就等于字符串的长度。

3.进位、借位的处理

加法进位:

c[i]=a[i]+b[i];
if(c[i]>=10){
	c[i]%=10;
	c[i+1]++;
}

减法借位:

if(a[i]<b[i]){
	a[i+1]--;
	a[i]+=10;
}
c[i]=a[i]-b[i];

乘法进位:

c[i+j-1]=a[i]*b[i]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;

4.商和余数的求法

视被除数和除数的位数情况进行处理。

例题1:

【题目描述】

求两个不超过200位的非负整数的和。

【输入】

有两行,每行是一个不超过200位的非负整数。

【输出】

一行,即相加后的结果。

【样例输入】

22222222222222222222
33333333333333333333
【样例输出】

55555555555555555555

以下是代码:


#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[10010],b[10010],c[10010];
int main(){
	cin>>s1>>s2;
	a[0]=s1.length();
	for(int i=1;i<=a[0];i++)a[i]=s1[a[0]-i]-'0';
	b[0]=s2.length();
	for(int i=1;i<=b[0];i++)b[i]=s2[b[0]-i]-'0';
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=c[0];i++){
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;
	}
	if(c[c[0]+1]!=0)c[0]++;
	for(int i=c[0];i>=1;i--)cout<<c[i];
	cout<<endl;
	return 0;
}

例题2:

【题目描述】

求两个大的正整数相减的差。

【输入】

共2行,第1行是被减数a,第2行是减数b(a > b)。每个大整数不超过200位,不会有多余的前导零。

【输出】

一行,即所求的差。

【样例输入】

9999999999999999999999999999999999999
9999999999999
【样例输出】

9999999999999999999999990000000000000

以下是代码:

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[10010],b[10010],c[10010];
int main(){
	cin>>s1>>s2;
	a[0]=s1.length();
	for(int i=1;i<=a[0];i++)a[i]=s1[a[0]-i]-'0';
	b[0]=s2.length();
	for(int i=1;i<=b[0];i++)b[i]=s2[b[0]-i]-'0';
	c[0]=a[0];
	for(int i=1;i<=c[0];i++){
		if(a[i]<b[i]){
			a[i+1]--;
			a[i]+=10;
		}
		c[i]=a[i]-b[i];
	}
	while(c[0]>1&&c[c[0]]==0)c[0]--;
	for(int i=c[0];i>=1;i--)cout<<c[i];
	cout<<endl;
	return 0;
}

本文内容为小编自己汇总,内容可能会有错误或疏漏,感谢大家的提议!

记得点赞和关注哦~

上一篇:高精度乘法


下一篇:洛谷 P1455 搭配购买