高精度运算

高精度加法

解析

实现高精度加法主要有2点：①怎么将数存下②怎么对数运算
一、怎么存下一个大整数？
答：存在数组当中，并从个位（低位）开始存。例如一个数123456789。

位置	0	1	2	3	4	5	6	7	8
存的数	9	8	7	6	5	4	3	2	1

（1）为什么要逆序存？
答：每次计算的时候，都有可能遇到进位的问题。如果在最大一位计算时出现了进位的情况，而我们又是使用正序存储，就需要移动数组在开头空出一个位置，这样会十分繁琐。所以直接使用逆序存储就可以十分方便的加上最后一位进位了。
而且这也符合我们人工计算的方向。（后面会解释人工计算）
（2）为什么使用动态数组（vector）
答：在动态数组中，可以使用STL自带的函数来很方便的获取数组长度，不用另外来求和存储，而且可以随机访问。
二、怎么对数组进行计算？
答：模拟人工加法,从两个数低位开始相加，当相加小于10时候直接表示为这一位的运算结果，相加的大于等于10的时候将大于10的部分作为这一位的运算结果并向前进一位。

模板

vector<int> add(string a,string b){
    
    vector<int>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');
    vector<int>C;
    int t=0;//进位标识，初始进位0
    for(int i=0;i<A.size()||i<B.size();i++){
    
        if(i<A.size())t+=A[i];//当前位存在，加入t
        if(i<B.size())t+=B[i];
        C.push_back(t%10);//将非进位数加入数组。
        t/=10;//当t大于10时商1，即为进位。
    }
    if(t)C.push_back(1);//判断最后是否进位
    return C;
}

例题

791. 高精度加法 - AcWing题库
AC题解：

#include <iostream>
#include <vector>
using namespace std;

vector<int> add(string a,string b){
    
    vector<int>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');
    vector<int>C;
    int t=0;//进位标识，初始进位0
    for(int i=0;i<A.size()||i<B.size();i++){
    
        if(i<A.size())t+=A[i];//当前位存在，加入t
        if(i<B.size())t+=B[i];
        C.push_back(t%10);//将非进位数加入数组。
        t/=10;//当t大于10时商1，即为进位。
    }
    if(t)C.push_back(1);//判断最后是否进位
    return C;
}

int main(){
    
    string a,b;
    cin>>a>>b;
    auto sum=add(a,b);//auto可以自动判断返回值类型，可以偷懒。
    for(int i=sum.size()-1;i>=0;i--)cout<<sum[i];
    return 0;
}

高精度减法

解析

​ 四种高精度算法的存储方式是相同的。

	$A_3$	$A_2$	$A_1$	$A_0$
—		$B_2$	$B_1$	$B_0$

$A_i-B_i-t$有两种情况，

①$A_i-B_i-t\ge 0$有直接$A_i-B_i-t$。

②$A_i-B_i-t<0$有$A_i-B_i+10-t$，同时要记录一个借位。

这时候可以发现一个问题，只有当保证$A\ge B$时候才能以一个正确的顺序计算。所以我们还需要考虑当$A<B$的情况，这种情况也很好处理只需要改成$-(B-A)$就可以了。这里当然还有一点，就是$A$和$B$一定都是正数，若是出现负数的情况还需要一个判断在转化。

• 总结：判断$A$和$B$的大小关系，$A\ge B$的时候算$A-B$；$A<B$的时候算$-(B-A)$。

最后还需要去除前导0。

模板

bool cmp(vector<int> &A,vector<int> &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;
}
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();//去除前导0
    return C;
}
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';

例题

792. 高精度减法 - AcWing题库

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &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;
}
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();//去除前导0
    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');
    vector<int> C;
    if(cmp(A,B))C=sub(A,B);
    else C=sub(B,A),cout<<'-';
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl;
    return 0;
}

高精度乘法

解析

​ 这里的高精度乘法和前面的高进度加法和除法不同，不是两个高精度相运算。而是一个高精度和一个低精度的运算。这里的低精度是小于$max(longlong)/10$的。

		$A_2=1$	$A_1=2$	$A_0=3$
$\times$				$B=12$
进位	$t_3$	$t_2$	$t_1$	$t_0$
值	$C_3$	$C_2$	$C_1$	$C_0$

第一步：

$C_0=(A_0\ast B+t_0)\%10=6$

$t_1=(A_0\ast B+t_0)/10=0$

第二步：

$C_1=(A_1\ast B+t_1)\%10=7$

$t_2=(A_1\ast B+t_1)/10=2$

第三步：

$C_2=(A_2\ast B+t_2)\%10=4$

$t_3=(A_2\ast B+t_2)/10=1$

第四步：

$C_3=(0\ast B+t_3)\%10=1$

• 最终答案$123\ast 12=1476$

模板

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();//去除前导0
    return C;
}
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');

例题

793. 高精度乘法 - AcWing题库

#include <iostream>
#include <vector>
using namespace std;
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();//去除前导0
    return C;
}
int main(){
    
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    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;
}

高精度除法

解析

​ 和高精度乘法一样，高精度除法也是高精度和低精度的运算。并且设定上不会产生小数，而是以余数的方式存在。

模板

vector<int> div(vector<int> &A,int b,int &r){
    //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;
}

例题

794. 高精度除法 - AcWing题库

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r){
    //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;
}
int main(){
    
    string a;
    vector<int> A;
    int B;
    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--)cout<<C[i];
    cout<<endl<<r<<endl;
    return 0;
}