大整数的存储方式

大整数以数组的方式储存，把每一位都存进数组，把个位存进低位数组，即倒着存。目的是方便进位，只需在数组后面再添加一个元素即可。

高精度加法

模拟加法运算的竖式，两个数组中的数分别相加，定义一个变量来模拟进位

加法模板

#include <iostream>
#include <vector>

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 /= 10;
    }
    if (t)									//进到了最高位，加一位数
        C.push_back(1);
    return C;
}

int main()
{
    string a, b;
    cin >> a >> 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');
    auto C = add(A, B);						//auto 关键字，自动识别类型

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

    return 0;
}

高精度减法

减法同样是遵循竖式运算的方式，相较于加法，需要处理的点从进位变成了借位

需要注意的点

借位的实现方法。
保证是大数减去小数，所以减之前要先判断两个数的大小
减完之后注意处理前缀零，比如 199 - 198 = 001 ，最后的答案要把前面的零除掉。

减法模板

#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;							//全都一样，大小相等，0，不用加负号
}

vector<int> sub(vector<int> &A, vector<int> &B)
{		
    vector<int> C;							//定义一个每个循环开始的时候值是0或1的t来表示借位
    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);			//(t + 10) % 10可以同时处理借位与不借位的情况
        if (t < 0)							//标记是否借位了
            t = -1;
        else
            t = 0;
    }

    while (C.size() > 1 && C.back() == 0)	//如果不是只有一位 0 ，且前导有的时，去掉前导零
        C.pop_back();

    return C;
}
int main()
{
    string a, b;								//输入大数与储存
    cin >> a >> 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');
    if (cmp(A, B))								//判断两个数的大小，决定用谁减谁
    {
        auto C = sub(A, B);

        for (int i = C.size() - 1; i >= 0; i--)
            printf("%d", C[i]);
    }
    else
    {
        auto C = sub(B, A);						//小数减去大数，前面加上一个零
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--)
            printf("%d", C[i]);
    }
    return 0;
}

高精度乘法

这里的高精度乘法指的是一个大数乘一个小数，并不是一个大数乘一个大数。

同样的模拟竖式的乘法。和加法是类似进位机制。

代码模板

#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();

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

高精度除法

同样是一个高精度的数除以一个低精度的数

同样是模拟竖式计算除法的每一步

代码模板如下

#include <iostream>
#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];						//每一次除完接下一位数，即余数 *10 ，加上下一位数
        C.push_back(r / b) ;					//上商
        r %= b;									//得余数

    }

    reverse( C.begin() , C.end());				//因为C队列里的数是正向排进的，为了与一般储存习惯相同，将其反向一下。

    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');
    int r;									//除法还要多一个余数
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--)
        printf("%d", C[i]);
    printf( "\n") ; 
    printf( "%d" , r);
    return 0;
}

SnowDawn'Home

C++高精度算法