高精度算法I(加,减法)

璃光（仆茜双厨）

2024-06-22 10:14:34

发布于：广东

35阅读

0回复

0点赞

本文均已同步CSDN账号&微博账号,目录见求建议-Ysjt | 唐 ™

一. 什么是高精度算法:

所谓的高精度算法指的是一般来说就是longlong无法解决的问题,一般的高精度算法分别为高精度加法, 高精度减法, 高精度乘法, 高精度除法,今天我们就开将高精度加减法

二. 高精度加法:

一般的高精度加法是一位一位的加,不存在进位,不过这种类型有很明显的局限性,比如当我们计算”1390349405930596094509405+4457842912833947289=?”这道题时,就必须要进位,我们必须要让电脑懂我们的指令,这也就对应了代码中的两层循环^[1]:

for (int i = a.size()-1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size()-1; i >= 0; i--) B.push_back(b[i] - '0');

也许有人会问为什么为什么要给A,B中加a的字符值-0,这就要说到c++的一个知识点:字符串
字符串中的第i个字符的ASCII码值减去0的ASCII码值,相减后的差值就是第i个字符本来所要表示的数字
那么接下来给出例题:
A633.高精度A+B
~~说实话Python是可以毁掉高精度的~~
^[2]

#include<iostream>
#include<vector>
using namespace std;
 
vector<int> add(vector<int>& A, vector<int>& B)
{
    vector<int> C;
    int t = 0;    //进位
    for (int i = 0; i <= A.size() - 1 || i <= B.size() - 1; i++)
    {
        if (i <= A.size() - 1) t += A[i];
        if (i <= B.size() - 1) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    //注意最高位的进位
    if (t)
        C.push_back(1);
 
    return C;
}
 
int main()
{
    string a, b;
    cin >> a >> b;  //a=121345
 
    //容器存放两个长整数
    vector<int> A, B;
 
    for (int i = a.size()-1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size()-1; i >= 0; i--) B.push_back(b[i] - '0');
 
    auto C = add(A, B);
 
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
 
 
 
    return 0;
}

三. 高精度减法:
在读小学时，我们做减法都采用竖式方法，如图 1 所示。这样，我们可以写出两个整数相减的算法。
我们就可以用 C++ 语言来模拟这个竖式减法的过程。我们可以考虑利用 C++ 的数组来存储对应数据，假设用数组 A 存储被减数 856 的每一位，具体来说就是 A1 存储个位 6，A2 存储十位 5，A3存储百位 8；类似数组 A 的结构，使用数组 B 存储减数 257；类似数组 A 的结构，使用数组 C 来存储对应的差 599。这样理论上来说，我们就可以计算无限大的数据。如上图 2 所示，下表表示对应的存储方式。

	数组A	数组B	数组C
[0]	6	7	9
[1]	5	5	9
[2]	8	2	5

总结：利用数组存储，突破存储的限制。每个位置存储 0 ~ 9 之间的数据。
例题:A7871.高精度减法
个人代码(不好见谅!):

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N],b[N],c[N],d;
bool cmp(string s1,string s2){
	int lena = s1.size();
	int lenb = s2.size();
	if(lena>lenb){
		return false;
	}else if(lena==lenb){
		for(int i=0;i<lena;i++){
			if(s1[i]<s2[i]){
				return true;
			}else{
				return false;
			}
		}
	}else{
		return true;
	}
}
int main(){
	string s1,s2;
	cin>>s1>>s2;
	if(cmp(s1,s2)){
		swap(s1,s2);
		cout<<"-";
	}
	int lena = s1.size();
	int lenb = s2.size();
	for(int i=0;i<lena;i++){
		a[i] = s1[lena-i-1] - '0';
	}
	for(int i=0;i<lenb;i++){
		b[i] = s2[lenb-i-1] - '0';
	}
	for(int i=0;i<lena;i++){
		c[i] += a[i] - b[i];
		if(c[i]<0){
			c[i] = 10+c[i];
			c[i+1] = -1;
		}
	}
	while(true){
		if(c[lena-1]==0 && lena>1) lena--;
		else break;
	}

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