【算法】高精度
作者:指针不指南吗
专栏:算法篇🐾不能只会思路,必须落实到代码上🐾
文章目录
- 前言
- 一、高精度加法
- 二、高精度减法
- 三、高精度乘法
- 四、高精度除法
前言
高精度即很大很大的数,超过了 long long 的范围,不能直接读取进行运算,需要用 string 读入,然后存储在数组中去。
高精度算法即把每一位上的数单独拿出来,分别计算,再跟每一位之间的关系,再研究,最后结果仍然存在数组中并输出。
一、高精度加法
-
思路
- 大整数的存储
- 使用 vector 存储,a[0] 存储个位,依次往后最后存储最高位
- 代码思想
- 从个位数开始依次,让a,b每一位相加,结果取模存在结果数组C中,t 表示进位
- 每次两个数a,b的各个位相加再加上进位t
- 直到加到最高位
- 大整数的存储
-
模板
#include<bits/stdc++.h> using namespace std;//C=A+B vector<int> add(vector<int> &A,vector<int> &B)//引用减少时间,不使用引用即把原数据copy一遍,费时间 {vector<int> C; //定义一个结果答案if(A.size()<B.size()) return add(B,A);int t=0; //t表示进位,个位开始,无需+进位,即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); t/=10; //求进位 } if(t) C.push_back(1); //离开循环时,t没有加 return C; }int main() {string a,b;vector<int> A,B;cin>>a>>b; //输入123456//存储大整数 倒着存储 for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0'); //存储 6,5,4,3,2,1for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0'); //注意这里是字符串的长度aauto C=add(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]); //注意 倒序输出return 0; }
二、高精度减法
-
思路
- 大整数的存储
- 核心思想
- 确保是大数减小数,首先从个位开始作差,取模存储在C中,t 表示借位(
这里很巧妙具体看下面的代码
) - 每次各个位上的数作差 - 借位 t ,取模存起来,有借位 t=1,没有t=0;
- 直到 大整数.size( )
去前导0
- 确保是大数减小数,首先从个位开始作差,取模存储在C中,t 表示借位(
-
模板
#include<bits/stdc++.h> using namespace std;//判断两个大整数的大小 bool cmp(vector<int> &A,vector<int> &B){ if(A.size()!=B.size()) return A.size()>B.size(); //位数不同时 if(A.size()==B.size()) //位数相同时 for(int i=0;i<A.size();i++)if(A[i]!=B[i]) return A[i]>B[i]; }//C=A-B vector<int> sub(vector<int> &A,vector<int> &B) {if(!cmp(A,B)) {cout<<'-'; //如果小减去大数:注意加个 - 负号 return sub(B,A); //交换 }vector<int> C;int t=0; //t表示借位 for(int i=0;i<A.size();i++){t=A[i]-t; //各个位上的数,先减去借位if(i<B.size()) t-=B[i]; //B还有数的话,减去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(); //去掉前导0 如003 return C; }int main() {string a,b;vector<int> A,B;cin>>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=sub(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;}
三、高精度乘法
高精度乘法一般是 一个大整数乘一个比较小的数
-
思路
-
大整数的存储
-
核心思想
- 小的数b不拆,让b依次和大数A的每一位相乘
从A的个位开始
,t表示进位; - 对每次计算
A[i]*b+t
的结果取模,存在结果数组中,借位除10即可,t可以任意大,比如可以进位22 - 直到 大数的最高位&&t==0
去掉前导0
- 小的数b不拆,让b依次和大数A的每一位相乘
- 模板
#include<bits/stdc++.h> using namespace std;//C=A*b vector<int> mul(vector<int> &A,int b) {vector<int> C;int t=0; //t表示进位for(int i=0;i<A.size()||t;i++){ //两个条件都满足才能退出来,否则没有计算完t=A[i]*b+t; //A的每一位与b相乘加上进位C.push_back(t%10); //对计算结果取模,存在结果数组中t/=10; }while(C.size()>1&&C.back()==0) C.pop_back(); //去掉前导0return C; }int main() {string a;int b; // 小的数用int 来存就OKvector<int> A;cin>>a>>b;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--) printf("%d",C[i]);return 0;}
-
四、高精度除法
高精度除法一般是一个大的整数除以一个小的整数
-
思路
- 大整数的存储
- 核心思想
- 从最高位开始,最高位除以除数,余数r剩下;
- r*10+大整数的下一位,再除以除数,余数r剩下;
- 重复,直到个位
去掉前导0
-
模板
#include<bits/stdc++.h>
using namespace std;//A➗b=C...r
vector<int> div(vector<int> &A,int b,int &r)
{vector<int> C;r=0; //r表示余数for(int i=A.size()-1;i>=0;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(); //去掉前导0return C;
}int main()
{string a;int b;vector<int> A;cin>>a>>b;for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');int r; //除法多个一个余数auto C=div(A,b,r);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);printf("\n");printf("%d",r);return 0;}
