算法基础学习笔记——③高精度

命运之光

发布于 2024-03-20 10:51:01

1200

发布于 2024-03-20 10:51:01

文章被收录于专栏：我在本科期间写的文章

✨博主：命运之光 ✨专栏：算法基础学习

前言：算法学习笔记记录日常分享，需要的看哈O(∩_∩)O，感谢大家的支持！

✨高精度

✨大致分类：

1.大整数存储（用数组存，每一位存一位数字）//从个位数字开始存，最后一位存最高位（方便进行进位等运算）

✨高精度加法

🍓高精度加法模板：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
     if (A.size() < B.size()) return add(B, A);
     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);
         t /= 10;
     }
     if (t) C.push_back(t);
     return C;
}

✨高精度减法

🍓高精度减法模板：

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
     vector<int> C;
     for (int i = 0, t = 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;
         else t = 0;
     }
     while (C.size() > 1 && C.back() == 0) C.pop_back();
     return C;
}

✨高精度乘以低精度

🍓高精度乘以低精度模板：

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int 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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

✨高精度除以低精度

🍓高精度除以低精度模板：

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &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 %= b;
     }
     reverse(C.begin(), C.end());
     while (C.size() > 1 && C.back() == 0) C.pop_back();
     return C;
}

🍓高精度加法模板（2）

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> add(vector<int> a,vector<int> b){
    vector<int> res;
    int t=0;
    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];
        res.push_back(t%10);
        t=t/10;
    }
    if(t)
        res.push_back(1);
    return res;
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    vector<int> a,b;
    for(int i=s1.length()-1;i>=0;i--)
    	a.push_back(s1[i]-'0');
    for(int i=s2.length()-1;i>=0;i--)
    	b.push_back(s2[i]-'0');
    vector<int> ans=add(a,b);
    for(int i=ans.size()-1;i<0;i++)
    	cout<<ans[i];
}

🍓高精度减法模板（2）

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(const vector<int> &a,const vector<int> &b){//a比b大时返回true 
    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> res;
    int t=0;
    for(int i=0;i<a.size();i++){
        t=a[i]-t;
        if(i<b.size())
        	t-=b[i];
        res.push_back((10+t)%10);
        if(t<0)
        	t=1;
        else
        	t=0;
    }
    while(res.size()>1&&res.back()==0)
    	res.pop_back();
    return res;
} 
int main(){
    string s1,s2;
    cin>>s1>>s2;
    vector<int> a,b;
    for(int i=s1.length()-1;i>=0;i--)
    	a.push_back(s1[i]-'0');
    for(int i=s2.length()-1;i>=0;i--)
    	b.push_back(s2[i]-'0');
    vector<int> ans;
    if(compare(a,b)){
    	ans=sub(a,b);
    }
    else{
    	ans=sub(b,a);
    	printf("-");
    }
    for(int i=ans.size()-1;i>=0;i--){
    	cout<<ans[i];
    }
    return 0;
}

🍓高精度乘法模板（2）

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
vector<int> mul(vector<int> A,int b){
    int t=0;
    vector<int> C;
    for(int i=0;i<A.size();i++){
        t+=A[i]*b;
        C.push_back(t%10);
        t=t/10;
    }
    while(t){
        C.push_back(t%10);
        t=t/10;
    }
    return C;
}
int main(){
    vector<int> A;
    int b;
    string s;
    cin>>s>>b;
    for(int i=s.length()-1;i>=0;i--){
    	A.push_back(s[i]-'0');
    }
    vector<int> ans=mul(A,b);
    for(int i=ans.size()-1;i>=0;i--){
    	cout<<ans[i];
    }
}

🍓高精度除法模板（2）

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> A,int b,int &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;
    }
    while(C.size()>1&&C.front()==0)
    	C.erase(C.begin());
    return C;
}
int main(){
    vector<int> A;
    int b,r;
    string s; 
    cin>>s>>b;
    for(int i=s.length()-1;i>=0;i--){
        A.push_back(s[i]-'0');
    }
    vector<int> ans=div(A,b,r);
    for(int i=0;i<=ans.size()-1;i++){
        cout<<ans[i];
    }
    if(r!=0){
        cout<<endl;
        cout<<"有余数:"<<r<<endl; 
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-27，如有侵权请联系 cloudcommunity@tencent.com 删除

vector