高精度算法I(加,减法)
2024-06-22 10:14:34
发布于：广东
本文均已同步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;
}
相关引用:
C++中的高精度运算-CSDN
「学习笔记」C++ 高精度算法
C++的高精度减法
代码选自:C++中的高精度运算-CSDN ↩︎
代码选自:C++中的高精度运算-CSDN ↩︎
有帮助，赞一个