算法学习之路 高精度算法

 //高精度加法模板

 #include<bits/stdc++.h>
using namespace std;

vector<int>add(vector<int>  &A,vector<int>&B)
{
    vector<int>C;
    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];
        C.push_back(t%10);
        t = t/10;
    }
    if(t)
    C.push_back(t);
    return C;
}
int main()
{
    string a;
    string b;
    vector<int>A;
    vector<int>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 = add(A,B);
    for(int i = C.size()-1;i >= 0;i–)
    cout<<C[i];
   return 0;
}
 
 
 
//高精度减法模板

 #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();
    else
    {
        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;
    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)
    {
        /* code */
        C.pop_back();
    }
    return C;
 }
int main()
{
    string a;
    string b;
    vector<int>A;
    vector<int>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’);
    if(cmp(A,B))
    {
        vector<int> C = sub(A,B);
        for (int i = C.size()-1; i >= 0;i–)
        {
            /* code */
            cout<<C[i];
        }
    }
    else
    {
        vector<int> C = sub(B,A);
        for (int i = C.size()-1; i >= 0; i–)
        {
            /* code */
            cout<<C[i];
        }
       
    }
       
   return 0;
}
 //高精度乘法模板

 #include<bits/stdc++.h>
using namespace std;
 vector<int> mul(vector<int> &A,int b)
 {
    vector<int>C;
    int t = 0;
    for(int i = 0;i <= A.size()-1;i++ )
    {
        t += A[i]*b;
        C.push_back(t%10);
        t /= 10;
    }
    if(t) C.push_back(t);
    return 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’);
    auto C = mul(A,b);
    for(int i = C.size()-1 ;i >= 0 ;i–)
    {
        cout<<C[i];
    }

   return 0;
}
 //高精度除法模板

#include<bits/stdc++.h>
 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 %= b;
    }
    reverse(C.begin(),C.end());
    while (C.size() > 1 && C.back() == 0)
    {
        /* code */
        C.pop_back();
    }
   

    return C;
 }
int main()
{
    string a;
    int b;
    int r;//余数
    vector<int>A;
    cin>>a>>b;
    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;
    cout<<r;
   return 0;
}