河北大学暑期程序设计训练每日知识分享-day25

每日分享——高精度运算

高精度就是说参与运算的数据和运算结果的范围，超出标准数据类型能表示的数据大小范围的运算。这个时候，如果要得到正确的计算结果，显然不能依靠普通方法实现了。而要在普通运算原理的基础上，加以辅助算法来实现超大数据的计算。例如：求两个100位的数据的和，或者计算两个100位的数字乘积。这时就要用到高精度算法了

高精度加法

C从0到C .size( )为低位到高位

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> add( vector<int> &A, vector<int> &B ) {
    if ( A.size() < B.size()) return add(B,A);
    int t = 0;
    vector<int> C;
    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;
}

高精度减法

比较A,B位数大小函数
（高精度减法需保证A位数大于B，若A<B, 则先计算B-A再加上括号）

1
2
3
4
5
6
7
8
9
bool cmp( vector<int> &A, vector<int> &B ) {
    if ( A.size() != B.size()) return A.size() > B.size();
    // 未返回则说明A,B位数相同
    // 从高位开始比较,直到遇到一个不同的数再比较大小
    for ( int i = A.size()-1; i>=0; i-- ) {
        if ( A[i] != B[i] ) return A[i] > B[i]; 
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> sub( vector<int> &A, vector<int> &B ) {
    vector<int> C;
    //  t表示借位，为0或1
    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;
    }
    // 去掉前导0
    while ( C.size() > 1 && C.back() == 0 ) C.pop_back();
    return C;
}

高精度乘法（大数乘小数）

一个大数×一个小数
对于A的每一位数都跟整个b相乘而不是一位一位计算

1
2
3
4
5
6
7
8
9
10
11
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;
}

高精度除法（大数除小数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// r 存储余数
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;
    }
    // C存储由高位到低位
    reverse(C.begin(), C.end());
    while ( C.size() > 1 && C.back() == 0 ) C.pop_back();
    return C;
}