【算法】高精度

作者：指针不指南吗
专栏：算法篇

🐾不能只会思路，必须落实到代码上🐾

前言

​ 高精度即很大很大的数，超过了 long long 的范围，不能直接读取进行运算，需要用 string 读入，然后存储在数组中去。

​ 高精度算法即把每一位上的数单独拿出来，分别计算，再跟每一位之间的关系，再研究，最后结果仍然存在数组中并输出。

---

一、高精度加法

1. 思路

   • 大整数的存储
     • 使用 vector 存储，a[0] 存储个位，依次往后最后存储最高位
   • 代码思想
     • 从个位数开始依次，让a,b每一位相加，结果取模存在结果数组C中，t 表示进位
     • 每次两个数a,b的各个位相加再加上进位t
     • 直到加到最高位

2. 模板

   #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;
   }
   

---

二、高精度减法

1. 思路

   • 大整数的存储
   • 核心思想
     • 确保是大数减小数，首先从个位开始作差，取模存储在C中，t 表示借位（这里很巧妙具体看下面的代码）
     • 每次各个位上的数作差 - 借位 t ，取模存起来，有借位 t=1，没有t=0;
     • 直到 大整数.size( ) 去前导0

2. 模板

   #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;} 
   

---

三、高精度乘法

高精度乘法一般是 一个大整数乘一个比较小的数

1. 思路

   • 大整数的存储

   • 核心思想

     • 小的数b不拆，让b依次和大数A的每一位相乘从A的个位开始，t表示进位；
     • 对每次计算A[i]*b+t的结果取模，存在结果数组中，借位除10即可，t可以任意大，比如可以进位22
     • 直到 大数的最高位&&t==0去掉前导0

   2. 模板

   #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;} 
   

---

四、高精度除法

高精度除法一般是一个大的整数除以一个小的整数

1. 思路

   • 大整数的存储
   • 核心思想
     • 从最高位开始，最高位除以除数，余数r剩下；
     • r*10+大整数的下一位，再除以除数，余数r剩下；
     • 重复，直到个位去掉前导0

2. 模板

#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;}