【C/C++】【高精度算法】1、高精度加法
一、为什么需要高精度算法
我们应该也有必要知道数据类型是有长度的吧。
比如32位?那位是?01一组01的二进制就是1位,8个1位放在一起叫做一个字节。
我们还记得int类型是4个字节,之前可能不知道啥意思,那放在这里,4*8是不是恰好等于32?
那32就是int类型的长度。很多情况下int类型是不能满足大数计算的。例如:计算 12345678901234567890 + 98765432109876543210
在很多情况下,普通的数据类型如int
、long long
等无法满足对极大整数进行计算的需求。比如计算非常大的阶乘、进行超大数的加法、乘法等运算时,就需要高精度算法来准确地处理这些数值。
-
超出数据类型范围
- C++ 中的普通数据类型如
int
、long long
等都有一定的表示范围。当需要处理的整数超出这个范围时,就无法使用普通的数据类型进行计算。 - 例如,计算两个非常大的数的和,如 12345678901234567890 + 98765432109876543210,普通的数据类型无法存储和计算这样的大整数。
- C++ 中的普通数据类型如
-
准确性要求
- 在一些应用场景中,需要精确的计算结果,不能有任何误差。高精度加法运算可以确保计算的准确性,不会因为数据超出范围而出现溢出或错误的结果。
- 比如在密码学、数值计算等领域,对计算结果的准确性要求非常高,高精度加法运算就显得尤为重要。
-
灵活性
- 高精度加法运算可以处理任意长度的大整数,不受数据类型的限制。这使得程序在处理大整数问题时更加灵活,可以适应不同的需求。
- 无论是计算非常大的整数,还是处理位数不确定的大整数,高精度加法运算都能提供可靠的解决方案。
其实这个过程就是把数字当作文字输入进来,再放进int数组中。然后利用算法计算两个int数组的和就完了。
让我们来详细学习一下吧:
高精度加法运算的步骤
-
数据存储
- 首先,将大整数用数组存储,数组的每个元素存储一位数字,通常从低位到高位依次存储。例如,整数 12345 可以存储为数组 [5,4,3,2,1]。
- 这样存储的好处是便于逐位进行运算和处理进位。
-
对齐操作
- 如果要相加的两个大整数位数不同,需要进行对齐操作。可以在较短的数前面补零,使得两个数的位数相同,方便后续的逐位相加。
- 例如,要计算 1234 和 987654,将 1234 表示为 [4,3,2,1,0,0],987654 表示为 [4,5,6,7,8,9]。
-
逐位相加
- 从低位向高位逐位相加。对于每一位,将两个数对应位上的数字相加,并加上前一位的进位值。
- 如果相加的结果小于 10,则直接将结果作为当前位的值,并且进位值为 0。
- 如果相加的结果大于等于 10,则将结果对 10 取余作为当前位的值,并且进位值为 1。
- 例如,计算上述对齐后的两个数,从最低位开始相加,0 + 4 = 4,没有进位;接着是 1 + 5 = 6,也没有进位…… 以此类推,直到最高位。
-
处理进位
- 当所有位都相加完毕后,如果进位值为 1,说明最高位有进位,需要在结果数组的最高位添加一个 1。
- 例如,在前面的例子中,如果最高位相加后有进位,结果数组应该是 [5,8,9,9,1,0,0]。
-
输出结果
- 最后,将结果数组从高位到低位输出,即为两个大整数相加的结果。
- 最后,将结果数组从高位到低位输出,即为两个大整数相加的结果。
详细代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn=250;
//stringA和b
char sa[maxn],sb[maxn];
//a原数组1,b原数组2,c加后的数组
int a[maxn],b[maxn],c[maxn];
int main(){
//sa是大数字1,sb是大数字2.字符串类型的
scanf("%s",sa);
scanf("%s",sb);
//第二步是把大数string,放到int数组中。
int la=strlen(sa);
int lb=strlen(sb);
for(int i=0;i<la;i++){
//倒着放,字符减去字符‘0’代表了一个数字本身
a[la-i-1]=sa[i]-'0';
}
for(int i=0;i<lb;i++){
//倒着放,字符减去字符‘0’代表了一个数字本身
b[lb-i-1]=sb[i]-'0';
}
//lc是新数组的长度
int lc=la>lb?la:lb;
for(int i=0;i<lc;i++){
c[i]=a[i]+b[i]+c[i];
//进位
if(c[i]>=10){
c[i+1]=c[i]/10;
//剩下的数存起来
c[i]=c[i]%10;
}
}
//看一下最后一位有没有进位,如果最后一位上的数字是大于0的,给再加一位
if(c[lc]>0)lc++;
//倒着输出c就好了
for(int i=lc-1;i>=0;i--){
printf("%d",c[i]);
}
//当然如果题中有说先导0,比如001+0004的情况
//可以去除先导0
cout<<endl;
int cnt=lc-1;
while(c[cnt]==0){
cnt--;
}
for(int i=cnt;i>=0;i--){
printf("%d",c[i]);
}
return 0;
}
当然这个过程只是帮助我们学习大整数的原理,我们还可以通过简单点的vector来实现。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 高精度加法函数
vector<int> add(vector<int> a, vector<int> b) {
vector<int> c;
int carry = 0; // 进位标志,初始为 0
for (size_t i = 0; i < max(a.size(), b.size()); ++i) {
int sum = carry; // 当前位的和初始为进位值
if (i < a.size()) sum += a[i]; // 如果 a 数组还有当前位,则加上
if (i < b.size()) sum += b[i]; // 如果 b 数组还有当前位,则加上
c.push_back(sum % 10); // 将当前位的和对 10 取余,得到当前位的结果存入结果数组 c
carry = sum / 10; // 更新进位值为当前位的和除以 10
}
if (carry > 0) c.push_back(carry); // 如果最后还有进位,则将进位存入结果数组
return c;
}
// 输出结果函数
void print(vector<int> v) {
for (auto it = v.rbegin(); it!= v.rend(); ++it) {
cout << *it; // 从高位到低位输出结果数组中的数字
}
cout << endl;
}
int main() {
string num1, num2;
cout << "输入第一个大整数:";
cin >> num1;
cout << "输入第二个大整数:";
cin >> num2;
vector<int> a, b;
for (int i = num1.length() - 1; i >= 0; --i) {
a.push_back(num1[i] - '0'); // 将输入的第一个大整数转换为数字数组,从低位到高位存储
}
for (int i = num2.length() - 1; i >= 0; --i) {
b.push_back(num2[i] - '0'); // 将输入的第二个大整数转换为数字数组,从低位到高位存储
}
vector<int> result = add(a, b);
print(result);
return 0;
}
原文地址:https://blog.csdn.net/qq_14840819/article/details/142980970
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!