五、练习：高精度

2022/8/6 23:25:01

编程Tag： int long s2 高精度 -- 练习 s1

本文主要是介绍五、练习：高精度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

高精度

今天我们就说一件事：高精度。
高精度是什么玩意儿？

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

好家伙，合着今天讲数学？
没错，我们今天直接梦回一年级，思考底层的加减乘除、四则运算。

数据类型的极大值、极小值

首先，在讲高精度以前，我们先来认识一下比较常见的几种类型的最大值、最小值。

最大值：
int类型：2147483647
char类型：127
short类型：32767
long类型：2147483647
long long类型：9223372036854775807
signed char类型：127
unsigned char类型：255
unsigned short类型：65535
unsigned int类型：4294967295
unsigned long类型：4294967295
unsigned long long类型：18446744073709551615


最小值：
char类型：-128
short类型：-32768
int类型：-2147483648
long类型：-2147483648
long long类型：-9223372036854775808
unsigned char类型：-128

大家没必要记，看看就OK了，有个大概的概念就行。
image

加法

加法这个事儿，大家肯定都很熟悉吧？

不是，我是说也许。
image

现在，我们来看看如何加。
image

很多人最开始一见到这个题，很高兴啊，“太简单了！我直接用long long”，然后就悲剧了。

我们想啊，题中给了一个条件：
image
那它肯定、肯定是不能使用常规的手法储存的，它的最大长度（501位）为远远超过 long long 类型的最大值。
我们要使用一些奇怪的东西，来储存它，比如说——字符串。

前面我们有说过，string类型没有长度限制，那我们可以怎么操作呢？

思路

通用的思路，我们来模拟一下如何进行加法运算。

我们可以知道，加法可能会有进位。
那进位能不能判断还不好说（很麻烦），所以我们考虑在数组中逆序存储，这样如果有进位会在结果的后面存储，最后输出时再 逆序输出 ，就实现了存储。
为了方便，我建议大家把数组的每一位设置为0，可能会方便些。

image

比如说，我们要计算 \(123 + 4567\) 。首先从用户那里输入进来，我们的字符串 \(s1\)、\(s2\) 的内容分别为 \(123\)、\(567\)。逆序存入数组储存：
image

然后，从0开始，遍历长度较长的数组，加法运算。
image

接下来，处理进位，逢十进一，当前的位取个位，后面的一位增加 \(1\) 。
image

从第 \(n\) 位倒着往回遍历，遇到第一个不是0的数时，就开始输出，得到 \(4690\) 。

image

哈哈哈，惊不惊喜，意不意外？
image

加法的代码实现

如下是刚才我手写的程序，大家可以看看；

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
// 用户输入的字符串
string s1,s2;
// a储存逆序s1，b储存逆序s2，c储存结果（考虑到进位，为了保证不会越界，开502的长度）
int a[501],b[501],c[502];
int main(){
	cin>>s1>>s2;
	// 逆序存入数组
	for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
	for(int i=0;i<s2.size();i++) b[i]=s2[s2.size()-i-1]-'0';
	// 加法计算
	int maxlen=max(s1.size(),s2.size()); // 获取较长的长度
	for(int i=0;i<maxlen;i++){
		c[i]+=a[i]+b[i];
		// 处理进位，不进位也不会受到影响
		c[i+1]+=c[i]/10, // 如果不进位，就不会加
		c[i]%=10; // 只取个位
	}
	// 获取第一个不是0的数
	bool flag=false; // 标记是否找到第一个不是0的数
	for(int i=maxlen+1;i>=0;i--){
	    if(c[i]||flag) flag=true; // 如果后面的一位不是0，就找到了第一个不是0的数；或者是已经找到了不是0的数，后面有0
		if(flag) cout<<c[i]; // 如果已经找到了第一个不是0的数，就连续地输出
	}
	if(flag==false) cout<<0; // 如果到最后一位也没找到不是0的数，结果是0
	return 0;
}

image

附上我以前初学时写的程序（可能过不了这个题，但是也是高精度），还是比较简单的：

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
	// 高精度加法 240位内
	int a[241]={},b[241]={},result[242]={},x=0,y=0;
	string c,d;
	cin>>c>>d;
	// 第一步读取整数
	for(int i=c.size()-1;i>=0;i--){
		a[x++]=c[i]-'0';
	}
	for(int i=d.size()-1;i>=0;i--){
		b[y++]=d[i]-'0';
	}
	// 第二步加法计算
	for(int i=0;i<(x>y?x:y);i++){
		result[i]+=(a[i]+b[i])%10;
		result[i+1]+=(a[i]+b[i])/10;
	}
	for(int i=(x>y?x:y);i>=0;i--){
		cout<<result[i];
	}
	return 0;
}

减法

减法和加法的算法差不太多，可以这样，你看，我们计算 \(123-45\)，可以这样：
image

我们借一当十，模拟：
例如下标为0的地方，可以这样计算：

\[10-5=5\\ 5+3=8 \]

OK，那就正常写呗：

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
	string s1,s2;
	int a[241]={},b[241]={},result[241]={},k=0,t;
	cin>>s1>>s2;
	// 考虑几种特殊情况
	if(s1==s2){  // 相等
		cout<<0;
		return 0;
	}
	// 后面的比前面的长，需要输出负号
	if(s1.size()<s2.size()||s1.size()==s2.size()&&s1<s2){
		cout<<"-";
		swap(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';
	}
	// 模拟竖式的算法
	for(int i=0;i<(s1.size()>s2.size()?s1.size():s2.size());i++){
	    t=10-b[i]+a[i]+result[k++];
		if(t<10) result[k]--; // 退位，在后面一位减去1
		result[k-1]=t%10;
	}
	// 前面可能有0，从第一个不是0的数开始输出
	for(int i=k-1;i>=0;i--){
		if(result[i]>0){
			t=i; // 记录第一个不是0的数的下标
			break;
		}
	}
	// 输出
	for(int i=t;i>=0;i--){
		cout<<result[i];
	}
	return 0;
}

乘法

这次，有点儿难度。
例题1：
image

例题2：
image

高精度乘单精度

高精度乘单精度，有个高级用法，即幂运算。
咳咳先别说那么多，该怎么算啊？？
image
假设我们要计算 \(123\times5\) ，给定高精度数s1（123）和单精度n（5），我们需要将高精度的每一位都乘上n，循环一遍；然后再处理进位。

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,a[501]={};
	string s1;
	cin>>s1>>n;
	for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
	for(int i=0;i<s1.size()+5;i++){
		// 按位相乘
		a[i]*=n;
	}
	for(int i=0;i<s1.size()+5;i++){
		// 处理进位
		a[i+1]+=a[i]/10,a[i]%=10;
	}
	// 输出
	bool flag=false;
	for(int i=s1.size()+5;i>=0;i--){
		if(a[i]||flag) flag=true;
		if(flag) cout<<a[i];
	}
	if(!flag) cout<<0;
	return 0;
}

我初学的时候这么写的：

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
	// 高精度乘单精度（不超过10000）
    int a[251]={};
    string s1;
	int b;
    cin>>s1>>b;
    for(int i=0;i<s1.size();i++){
		a[i]=s1[s1.size()-i-1]-'0';
	}
	// 按位相乘
	for(int i=0;i<s1.size();i++){
		a[i]=a[i]*b;
	}
	// 处理进位
	for(int i=0;i<s1.size()+4;i++){
		if(a[i]>=10){
			a[i+1]+=a[i]/10;
			a[i]%=10;
		}
	}
	// 获取第一个不是0的数
	int point=0;
	for(int i=s1.size()+4;i>=0;i--){
		if(a[i]!=0){
			point=i;
			break;
		}
	}
	for(int i=point;i>=0;i--){
		cout<<a[i];
	}
	return 0;
}

高精度乘高精度

这个部分比较难，计算高精度数\(s1\)、\(s2\)的乘积，即\(123\times456\)
image

按照正常的竖式计算法，我们应该用一个数去乘另一个数的每一位（单精度），所以我们需要双重循环。

// AUTHOR:PANDAOXI
#include <iostream>
using namespace std;
int main(){
 string s1,s2;
	int a[4002]={},b[4002]={},result[8004]={};
	cin>>s1>>s2;
	for(int i=0;i<s1.size();i++) a[i]=s1[s1.size()-i-1]-'0';
	for(int i=0;i<s2.size();i++) b[i]=s2[s2.size()-i-1]-'0';
	for(int i=0;i<s1.size();i++){
		for(int j=0;j<s2.size();j++){
			result[i+j]+=a[i]*b[j];
   			result[i+j+1]+=result[i+j]/10,
			result[i+j]%=10;
		}
	}
 	int p=0;
	for(int i=s1.size()+s2.size()-1;i>=0;i--){
		if(result[i]>0){
			p=i;break;
		}
	}
	for(int i=p;i>=0;i--){
		cout<<result[i];
	}
	return 0;
}

解例题

第一题，我们可以使用高精度乘单精度，单精度即2，高精度即2的幂。

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
	// 2的0次方=1
	int a[501]={1},len=1,p,n; // len=1,记录长度
	cin>>n;
	for(int i=0;i<n;i++){ // 乘n次2
		// 按位相乘
		for(int j=0;j<len;j++){
			a[j]*=2;
		}
		// 处理进位
		for(int j=0;j<len;j++){
			a[j+1]+=a[j]/10;
			a[j]%=10;
		}
		// 如果后面有个数，长度就要增加了
		if(a[len]>0) len++;
	}
	// 输出
	for(int i=len;i>=0;i--){
		if(a[i]>0){
			p=i;
			break;
		}
	}
	for(int i=p;i>=0;i--){
		cout<<a[i];
	}
	return 0;
}

说实话这个题根本用不着高精度，只是看着像，用高精度也能解。

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	cout<<(1<<n); // 左移一位（位运算）
	return 0;
}

例题二也不难，高精度乘高精度，直接套程序。注意观察数据范围。

高精度除法

计算\(a{\div} b\)（保留n位小数）。大家可以找找规律。

// Author:PanDaoxi
#include <iostream>
using namespace std;
int main(){
	int a,b,n,t=0,c[1001];
	cin>>a>>b>>n;
	// 输出小数点
	cout<<a/b<<".";
	a=(a%b)*10;
	// 计算小数点后的数
	for(int i=0;i<n;i++){
		c[t++]=a/b;
		a=(a%b)*10; // 当10，再算
	}
	// 输出
	for(int i=0;i<t;i++){
		cout<<c[i];
	}
	return 0;
}

关于打表

其实，告诉大家个坏消息，python自带高精度，C++就得手写……
image

例如这道题：
image

在竞赛中，Python可以当做工具使用，但不能作为程序提交。所以，我们可以结合Python（或其他语言、程序），把得到的结果储存在字符串数组中，这种行为就是打表。
打表虽然不讲武德，但是也有很多好处，我们要善于利用工具



这篇关于五、练习：高精度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程