高精度问题
目录
算法实现基础
高精度加法A+B
测试链接
源代码
代码重点
高精度减法A-B
测试链接
源代码
代码重点
高精度乘法A*b和A*B
测试链接
源代码
代码重点
高精度除法A/b和A/B
测试链接
源代码
代码重点
高精度求和差积商余
算法实现基础
本算法调用STL库函数vector容器来使用
vector库的详细用法可查看单链双链表以及vector 中的部分内容
建议学习过vector的使用方法之后再来看本算法文章
由于Java与Python等语言拥有特性可以不使用高精度算法实现
因此本篇文章主要讲解的是c++的高精度算法
高精度加法A+B
测试链接
洛谷P1601 A+B Problem（高精）
源代码
c++解法
代码重点
1.数字的存储为倒叙存储。就vector容器的特点来说，在头部插入元素的难度以及数据处理量要远远大于在尾部插入元素，因此对于长整数的存储来说，在vector容器当中倒叙存储(注意字符数组与字符数组的转换)，对于答案容器中的数字也是倒叙存储。
2.t的功能包括计算当前位数的和和为下一位的和做进位
3.如果t不为0时证明仍有进位，若此时答案数组全部已经计算完毕则证明要在最高位加一
4.auto类型的设定可以让系统根据函数的返回值类型自动对C进行类型限制
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{vector<int> C;int t = 0;if(A.size()<B.size())return add(B,A);for(int i = 0;i < A.size()||i < B.size();i ++ ){if(i < A.size())t += A[i];if(i < B.size())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;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 -- )cout<<C[i];return 0;
}Python解法
a=int(input())
b=int(input())
ans=a+b
print(ans)高精度减法A-B
测试链接
洛谷P2142 高精度减法
源代码
c++解法
代码重点
1.cmp函数，当大整数A和B的长度不相等时，比较二者长度即可。当二者长度相同时，从最高位依次向下比，当有其中一位不相等时，返回本位比较值即可。当各位都相等时，则返回ture。经过此函数的处理之后，若布尔函数返回true则为A>=B的情况。若布尔函数返回false则为A<B的情况
2.sub函数：t为借位情况，经过cmp函数的调整之后A一定是大于等于B的，所以从最低为开始减，若此位运算结果小于0，则加10再对10取余为本位结果，必向高位进行了借位，因此在下一位运算时-1。若此位运算结果大于等于0，则不进行借位，下次运算时t为0。在进行运算之后，要进行去掉前导0的运算
3.main函数，依旧本着方便运算的原则对于大整数进行倒叙存储，根据cmp函数结果进行分流，当true时为正，倒叙输出C即可。当false时为负，首先输出一个负号，再倒序输出即可
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B)
{if(A.size() != B.size())return A.size() > B.size();for(int i = A.size() - 1;i >= 0;i -- ){if(A[i] != B[i])return A[i] > B[i];}return true;
}
vector<int> sub(vector<int> &A,vector<int> &B)
{vector<int> C;int t = 0;for(int i = 0;i < A.size();i ++ ){t += A[i];if(i < B.size())t -= B[i];C.push_back((t + 10) % 10);if(t < 0)t = -1;else t = 0;}while(C.size() > 1 && C.back() == 0)C.pop_back();return C;
}
int main()
{string a,b;cin>>a>>b;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');if(cmp(A,B)){auto C = sub(A,B);for(int i = C.size() - 1;i >= 0;i -- )cout<<C[i];}else{cout<<"-";auto C = sub(B,A);for(int i = C.size() - 1;i >= 0;i -- )cout<<C[i];}
}Python3
a=int(input())
b=int(input())
ans=a-b
print(ans)高精度乘法A*b和A*B
测试链接
洛谷P1303 A*B Problem
源代码
c++解法（b为短数据）
代码重点
1.c++代码为大整数乘以小整数，因此对于洛谷的那道题来说只能通过40%的数据。高精度大乘小的原理在于A从最低为乘b乘到最高位，其中的t为进位，乘b之后当前位为(t + A[i] * b)%10，进位为((t + A[i] * b)%10)/10
2.其余依旧是大整数通过string和vector进行逆序存储逆序输出
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> mul(vector<int> &A,ll &b)
{vector<int> C;int t = 0;for(int i = 0;i < A.size() || t;i ++ ){if(i < A.size())t += A[i] * b;C.push_back(t % 10);t /= 10;}return C;
}
int main()
{string a;ll b;cin>>a>>b;vector<int> A;for(int i = a.size() - 1;i >= 0;i -- )A.push_back(a[i] - '0');auto C = mul(A,b);for(int i = C.size() - 1;i >= 0;i -- )cout<<C[i];return 0;
}Python3（B为长数据）
A*B太麻烦直接用Python3
a=int(input())
b=int(input())
ans=a*b
print(ans)高精度除法A/b和A/B
测试链接
洛谷P1480 A/B Problem
源代码
c++解法(b为短数据)
代码重点
1.与高精度加法、减法、乘法不同的是，高精度除法在div函数之中对于A的遍历顺序为从为到头，因存储时为倒叙存储，即为从最高位开始计算。所以，r作为一个余数来模拟人工算法，因一道题当中很可能不仅仅只对于除法进行考察，很有可能是四则运算，因此为了方便起见，C需要反转一下便于后面的输出，注意在反转之后要去掉前导零，因洛谷上的b为小整数小于10^9，因此能够通过所有数据测试点
2.部分题目可能要输出余数，因此将输出余数那一行的注释去掉就ok了
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<int> div(vector<int> &A,ll &b,ll &r)
{vector<int> C;r = 0;for(int i = A.size() - 1;i >= 0;i -- ){r = r * 10 + A[i];C.push_back(r / b);r = r % b; }reverse(C.begin(),C.end());while(C.size() > 1 && C.back() == 0)C.pop_back();return C;
}
int main()
{string a;ll b,r;cin >> a >> b;vector<int> A;for(int i = a.size() - 1;i >= 0;i -- )A.push_back(a[i] - '0');auto C = div(A,b,r);for(int i = C.size() - 1;i >= 0;i -- )cout<<C[i];//cout<<endl<<r;//此处输出的为余数return 0;
}Python3解法(B为长数据)
a=int(input())
b=int(input())
ans=a//b
print(ans)高精度求和差积商余
c++太太太太太头疼了还是Python3比较暴力省事
a=int(input())
b=int(input())
print(a+b)
print(a-b)
print(a*b)
print(a//b)
print(a%b)