高精度算法

高精度算法

1、高精度加法

描述：

求两个大正整数相加的和。

思路：

​ （1）用可变长数组vectorA，B存储

​ （2）将输入的大数用字符串a，b读入，并逆序存入A，B

​ （3）进行套用高精度模板

​ （4）最后逆序输出答案即可

代码模板：

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

const int N = 100010;

vector<int> A, B;
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 /= 10;
    }

    if (t) C.push_back(1);
    return C;
}

int main()
{
    string 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 = Add(A, B);

    for (int i = C.size() - 1;i >= 0; i--) printf("%d", C[i]);

    return 0;
}

注意：

最后可能会存在一位进位，需要特判，若存在直接push进答案最后即可

2、高精度减法

描述：

​ 求两个大正整数A，B的差。

思路：

高精度减法：大数A - 大数B
（1）用可变长数组vector存储A，B
（2）将字符串a、b逆序存入数组A、B中
（3）为了计算方便，我们再计算之前先保证较大的数减去较小的数，即我们要先判读出A、B谁大
（3.1）自定一个比较大小的cmp函数，用于返回若 A > B,返回true，反之返回false
（3.2）cmp函数的构造分为两种情况 位数相同 和 位数不同
（3.3）位数不同：肯定是位数长的数大
（3.4）位数相同，我们就需要从后向前遍历两个数组（因为我们已经逆序存储了），
找到第一个不相同的数进行比较，谁大，说明该数组表示的数大
（4）高精度减法的构造
（4.1）定义一个答案数组和临时变量t（存放借位）
（4.2）从前到后遍历较大数组（因为是逆序存储，所以原本低位相减变成了现在的前面的数相减）：
（4.3）每一次遍历，先让较大的数减去借位，然后再减去较小的数中（需要判读较小的数是否还剩于）
（4.4）因为有可能相减为负数，这里利用一个技巧直接将(t + 10) % 10的结果加入答案末尾即可，这里保证了加入的一定是相减结果的绝对值
（4.5）更新借位，
如果t为负数，说明在相减的时候，借位了，让 t = 1，表示借了一位，保留到下一次计算进行减去
如果t为正数，说明在相减的时候，没有借位，让借位置零即可
（4.6）最后再进行去前导0即可
如果答案的长度大于1，且答案最后有0，就将0弹出即可
（5）最后逆序输出答案即可

代码模板：

#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();
    else
    {
        for (int i = A.size() - 1; i >= 0; i --)
        {
            if (A[i] != B[i]) return A[i] > B[i];
        }
    }
    return 1;
}

vector<int> sub(vector<int> A, vector<int> B)
{
    vector<int> C;

    int t = 0;
    for (int i = 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;
}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> A, B, C;

    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)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];

    return 0;
}

注意：

​ （1）首先一定要保证是用大于减小数，故需要实现一个cmp函数

​ （2）其次由于保证了是大数减小数，故不存在剩一位的情况，一定能减得下，故一定会被存进答案里

​ （3）由于高位在后，低位在前，故有可能存在前导零，故需要取前导零。

3、高精度乘法

描述：

​ 求一个大正整数与一个数的乘积。

思路：

（1）用可变长数组vector存储A

（2）将字符串a逆序存入数组A中
（3）高精度乘法的构造：
（3.1）定义一个答案数组，并且初始化进位t
（3.2）从头到尾遍历大数A，
（3.3）将每一位与b的乘积的计算结果放入t中
（3.4）将t % 10的结果放入答案数组的末尾
（3.5）更新进位t
（3.6）看进位t是否还有数，如果还有，就在答案数组末尾加入该数
（3.7）去前导0
（4）逆序输出答案数组即可

代码模板：

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

    if (t) C.push_back(t);
    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');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];


    return 0;
}

注意：

​ （1）由于可能最后的答案可能为0，故需要去除前导零的情况。

​ （2）由于可能最后一位计算后大于了10，还没有进位，故需要判断是否还有剩位，有则直接放在答案末尾即可。

4、高精度除法

描述：

​ 求一个一个非负大整数A与一个整数b的商和余数。

思路：

高精度除法：大数A / 小数b
（1）用可变长数组vector存储A
（2）将字符串a逆序存入数组A中
（3）构造高精度除法
（3.1）定义答案数组，以及初始化余数t，由于余数最后要输出， 可以定义成全局变量
（3.2）从后往前遍历大数（大数是逆序存储到数组的，但这里除法需要从高位开始计算，所以从最后一位即大数的高位开始）
（3.3）每一位数 + 余数 * 10 ，进行计算
（3.4）将上一步的结果 除 b 的结果放入答案数组
（3.5）最后更新余数 t %= b
（3.6）将答案数组翻转，因为最后的输出是逆序输出的
（3.7）去前导0
（4）逆序输出答案数组即可

代码模板：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int t;
vector<int> div(vector<int> A, int b)
{
    vector<int> C;

    t = 0;

    for (int i = A.size() - 1; i >= 0; i --)
    {
        t = A[i] + t * 10;
        C.push_back(t / b);
        t %= b;
    }

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

    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
    cout << endl << t;
    return 0;

}

注意：

​ （1）由于做除法只能从高位做，且模板都是逆序存，逆序输出，为了统一模板，则在除法模板中写的有些复杂

​ （2）除法模板与其他模板不同，需要逆序逐位除，即高位往低位算

​ （3）算出来之后，由于我们需要逆序输出，故我们要将求出来的答案用reverse进行翻转

​ （4）然后由于可能前几位除不下，故需要进行去前导零。