|
自我介绍：大家好，我是小鱼，目前是一名本科大二的学生，这是我的第一篇，在接下来的日子里，我将会分类讲解各种不同的数据结构与算法，希望可以与大家共同进步，共同成长。
本章介绍：众所周知，在处理数与数的运算时，一旦两个数的位数超过了所使用文章的数据类型时，便会出现溢出（对于数的溢出，我们在后续的文章中会详细讲解）。为了应对这种情况，高精度算法应运而生。高精度算法是用于计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘等运算。（本章的代码已通过洛谷和ACWing的全部测试点）
4种数据类型及取值范围：
byte：-2^7~2^7-1? ?,即? -128~127，? 1字节
short：-2^15~2^15-1? ?,即-32768~32767 ，? ?2字节
有符号 int? : -2^31~2^31-1? ?,即-2147483648~2147483647，? ?4字节
无符号 int? : 0~2^32-1
long : -2^63~2^63-1? ?,即-9223372036854774808~9223372036854774807,? ?8字节
高精度加法
题目描述：
给定两个正整数a,b，计算它们的和。
输入格式：
共两行，每行包含一个整数。
输出格式：
输出只有一行，代表a+b的值
数据范围：
a,b≤10500
题目分析：
本题目是最基础的高精度题型，对于这类问题，我通常采用字符串处理。
核心点：与小学时做加法的步骤相似，一位一位的对着加，注意存储进位。
本题另一个核心点就是明白数字和字符串的区别在哪里，即个位数字在哪里
1.使用数字存储时，个位是字符串的最后一位；
2.两个字符串相加，因为字符串的长度可能不一致，所以最好翻转过来，这样字符串就变成了个位在前；
3.相加的过程即，定义一个s=0，用s分别与每个字符串的第i，j位相加，十位做下一次循环；
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N=100010;
string A,B;
string add(const string &A,const string &B){
string C;//C=A+B;
int s=0;
for(int i=A.size()-1,j=B.size()-1;i>=0||j>=0||s>0;i--,j--){
if(i>=0) s+=(A[i]-'0');
if(j>=0) s+=(B[j]-'0');
C+=((s%10)+'0');//用C来存储相加的结果
s=s/10;//去除掉s的个位，把s的十位放到下一次的循环中
}
reverse(C.begin(),C.end());
return C;
}
int main(){
cin>>A>>B;
cout<<add(A,B)<<endl;
return 0;
}
附上高精度加法的代码模板
string add(const string &A,const string &B){
string C;//C=A+B;
int s=0;
for(int i=A.size()-1,j=B.size()-1;i>=0||j>=0||s>0;i--,j--){
if(i>=0) s+=(A[i]-'0');
if(j>=0) s+=(B[j]-'0');
C+=((s%10)+'0');
s=s/10;
}
reverse(C.begin(),C.end());
return C;
}
高精度减法
题目描述：
给定两个正整数a,b，计算它们的差。
输入格式：
共两行，每行包含一个整数。
输出格式：
输出只有一行，代表a+b的值。
数据范围：
a,b≤10500
题目分析：
高精度减法的思想与高精度加法类似，可以用同一种思路写。但对减完之后0的后缀问题和字典序大小的比较仍需要讨论
核心思想：
1.同上面高精度加法，但对于类似30-30的问题，计算结果可能会出现00的情况，或输入003、10得到结果应为-8.面对这种情况，我们应该才用去0操作，分别在处理数据前，做去0操作，在计算后，对计算结果，做去0操作；
2.减法需要比较字典序的大小，字典序较大的应作为被减的一方，以防止出现倒序后高位不够减的情况；
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010;
bool cmp(vector<int> &A, vector<int> &B)//比较A，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;
}
void trimZero(vector<int> &A)//去0操作
{
while (A.back() == 0 && A.size() > 1) A.pop_back();//若A的最后一位是0且A至少有一位，去除A的0后缀
}
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] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;//t<0说明t向前借了一位
else t = 0;//否则把t置为0，进行下一位的运算
}
trimZero(C);
return C;
}
int main()
{
string a, b;
cin >> a >> b;
vector<int> A, B, C;
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');
trimZero(A), trimZero(B);//去后缀0
if (cmp(A, B)) C = sub(A, B);
else {
C = sub(B, A);
printf("-");
}
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
return 0;
}
附上高精度减法的代码模板
bool cmp(vector<int> &A, vector<int> &B)//比较A，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;
}
void trimZero(vector<int> &A)//去0操作
{
while (A.back() == 0 && A.size() > 1) A.pop_back();//若A的最后一位是0且A至少有一位，去除A的0
}
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] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;//t<0说明t向前借了一位
else t = 0;//否则把t置为0，进行下一位的运算
}
trimZero(C);
return C;
}
?
高精度乘法
题目描述
给定两个非负整数（不含前导?00）?AA?和?BB，请你计算?AA×BB?的值。
输入格式
共两行，第一行包含整数?AA，第二行包含整数?BB。
输出格式
共一行，包含?A×BA×B?的值。
数据范围
1≤A的长度≤100000，
0≤B≤10000
题目分析
高精度乘法与加法类似，在做题时可以参考小学时写乘法列的算式，可以写出C[i+j]+=A[i]*B[j],在计算完C[i]之后，可能会出现累加之后的C[i]并不是一位，而是两位数或三位数，这时就需要我们参考高精度加法中的模拟进位，最后因为是倒序，有可能出现前缀和为0，所以还要去掉前缀0。
核心思想
1.模拟乘法算式
2.模拟进位
3.去掉前缀0
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> mul(vector<int>&A,vector<int>&B){
vector<int> C(A.size()+B.size(),0);
for(int i=0;i<A.size();i++)
for(int j=0;j<B.size();j++)
C[i+j]+=A[i]*B[j];
int t=0;
for(int i=0;i<C.size();i++){//若C的某一位不是一位数，则考虑进位
t+=C[i];
C[i]=t%10;
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();//去掉前缀0
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 j=b.size()-1;j>=0;j--) B.push_back(b[j]-'0');
auto C=mul(A,B);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}
附上高精度乘法的代码模板
vector<int> mul(vector<int>&A,vector<int>&B){
vector<int> C(A.size()+B.size(),0);
for(int i=0;i<A.size();i++)
for(int j=0;j<B.size();j++)
C[i+j]+=A[i]*B[j];
int t=0;
for(int i=0;i<C.size();i++){//若C的某一位不是一位数，则考虑进位
t+=C[i];
C[i]=t%10;
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();//去掉前缀0
return C;
}
高精度除法
题目描述
给定两个非负整数（不含前导?00）?A，BA，B，请你计算?A/BA/B?的商和余数。
输入格式
共两行，第一行包含整数?AA，第二行包含整数?BB。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B?一定不为?0
题目分析
除法的高精度仍然是模拟做除法算式，重要的是如果高位不能整除，则可以在低位借一当十，然后再参与下一位的除法运算，最后仍要注意去除前缀0。
核心思想
1.高位余数在低位借一当十
2.去除前缀0
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int r=0;//表示余数
vector<int> div(vector<int> &A,int B,int &r){
vector<int> C;
for(int i=0;i<A.size();i++){
r=r*10+A[i];//若高位不能整除除数则可在低位借一当十
C.push_back(r/B);
r%=B;//表示每一位的余数
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();//去除前缀0
return C;
}
int main(){
string a;
int B;
cin>>a>>B;
vector<int> A;
for(int i=0;i<a.size();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;//输出余数
cout<<endl;
return 0;
}
附上高精度除法模板
vector<int> div(vector<int> &A,int B,int &r){
vector<int> C;
for(int i=0;i<A.size();i++){
r=r*10+A[i];//若高位不能整除除数则可在低位借一当十
C.push_back(r/B);
r%=B;//表示每一位的余数
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();//去除前缀0
return C;
}
总结
这篇文章讲解了高精度加法、减法、乘法和除法的求解方法关键点如下：
高精度加法
1.记住字符串中个位在后面，高位在前面，要把字符串翻转一下；
2.定义一个s=0，用s分别与每个字符串的第i，j位相加，十位做下一次循环；
高精度减法
1.前缀为0的情况要去0；
2.比较字典序的大小，字典序大的作为减数，注意借位；
高精度乘法
1.模拟乘法算式进位
2.去除前缀0
高精度除法
1.模拟除法算式借一当十
2.去除前缀0
|