OI学习笔记——[基础算法]高精度四则运算

所有完整代码均可在GitHub根据文章索引查找

0 题目描述

\(Kanwuqing\) 是一个算法小白, 学会了编程中的基础四则运算, 但他发现当进行运算的两个数大于 \(2^{63}-1\) 时, 运算结果会变得很奇怪. 他想设计一个四则运算计算器, 使得进行计算以及结果位数不大于 \(2^{63}-1\) 的数可以理论上进行计算

其中, 保证数字是整数, 且不会出现负数, 所有数字的位数不会超过 \(10^9\) 位

1 算法思路

首先是存储问题, 显然对于如此大的数字, 整数类型(哪怕是 unsigned long long)也存不下, 那么这个时候我们想到既然直接存数字不行, 那我们存字符串不就好了? 字符串完全可以接受那么多位

其次是计算问题, 对于字符串, 我们目前只会按位进行运算(不是位运算), 由此我们想到了可以模拟小学就会的竖式, 大概想一想时间复杂度并不高

2 算法实现

2.1 加法

首先来解决最直观最简单的加法问题, 我们要做的事情有:

  • 读入数字(以字符串形式)
  • 将字符串存入数组, 并将数组反转(字符串的0在首位, 但竖式中是从尾到头的)
  • 模拟竖式计算
  • 输出结果

首先是i(n) 

1
2
3
4
5
6
7
8
9
10
// 全局定义
const int N = 1e5 + 5;
int A[N], B[N], C[N], la, lb, lc;

// main函数
string a, b, c;
cin >> a >> b;
la = a.size();
lb = b.size();
lc = max(la, lb);  // 此处不用考虑首位进位, 加法结果最多比两个字符串的最大长度大1

然后处理字符串, 注意下标对应关系. 此处从 [0] 开始存, 当然也可以从 [1] 开始存

1
2
for(int i = la - 1; i >= 0; i--) A[la - 1 - i] = a[i] - '0';  // 如 la=3, a[2] = '3' 则 A[0] = 3
for(int i = lb - 1; i >= 0; i--) B[lb - 1 - i] = b[i] - '0';

然后是重点, 进行模拟竖式加法 

1
2
3
4
5
6
7
8
9
10
11
12
add(A, B, C);

// 全局中, 定义add
void add(int A[], int B[], int C[]){
    for(int i = 0; i < lc; i++){  // 计算结果的每一位
        C[i] += A[i] + B[i];  // 先加
        if(C[i] >= 10){  // 如果加完爆了
            C[i] -= 10;  // 模拟进位
            C[i + 1]++;
        }
    }
}

最后输出 

1
2
3
4
for(int i = lc - 1; i >= 0; i--) cout << C[i];
或
for(int i = lc - 1; i >= 0; i--) c += C[i] + '0';
cout << c;

2.1.1 动态数组实现

那么这时候就有人要问了: 要搞下标这也太烦了! 有没有什么省脑子的做法呢? 有的兄弟, 当然有的, 我们将上文中的数组变为 STL 中的 vector 容器就好了, 但有些地方需要修改: - 变长数组空位不再是 \(0\), 需要初始化为 \(0\) 或 判断该位是否有数字 - io语句要进行适当修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> A, B, C;

void add(vector<int> &A, &B, &C){
    int t=0;
    for(int i = 0; i < lc; i++){
        if(i < la) t += A[i];  // 位数没到再加, 规避了数组下标越界
        if(i < lb) t += B[i];
        C.push_back(t % 10);  // 存入结果的各位
        t /= 10;  // 结果保留十位进位, 进行下一轮
    }
    if(t) C.push_back(t);  // 最后可能会有进位
}

// main函数
for(int i = la - 1; i >= 0; i--) A.push_back(a[i] - '0');
for(int i = lb - 1; i >= 0; i--) B.push_back(b[i] - '0');
add(A, B, C);
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];

突然发现确实更爽, 但是仓库里加法代码已经写完了懒得改了, 从减法开始统一使用可变数组

2.2 减法

首先要明确减法可能会出现负数, 且可能会减出来一堆的 \(0\), 因此我们在这两步上要格外当心

对于第一个问题, 我们可以使用特殊判断(SpecialJudge), 先比较二者大小, 若前小后大, 则交换并输出负号. 然而这又引出第二个问题: 两个数太大, 该如何比较大小? 这需要我们自己写一个比较函数, 采取的同样是模拟人脑比大小, 从高到低比, 只要有一位更大就结束; 若位数不同, 则位数较大的直接获胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> A, B, C;

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

// 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');

if(!cmp(A, B)){
    swap(A, B);
    cout << '-';
}

接下来来到核心函数: 模拟减法. 这里分两步: - 和加法一样, 只不过将进位变成退位 - 去除前导 \(0\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void minus1(vector<int> &A, vector<int> &B){  // STL 中有内置的减法
    int t = 0;
    for(int i = 0; i < A.size(); i++){
        int t = A[i] - (i < B.size() ? B[i] : 0);  // 若没到 B 首位, 则减去
        if(t < 0){  // 退位
            t += 10;
            A[i + 1]--;
        }
        C.push_back(t);
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();  // 剔除结果中的前导零
}

// main函数
minus1(A, B);
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];

同样用的是可变数组写法, 但是前面那个没有用size函数, 而是预处理的l变量

2.3 乘法

从这里开始, 就有些让人头大了, 还是先回忆一下小学的时候是怎么做乘法的: 是将第二个数每一位都和第一个数做乘法, 然后再全部加起来. 然而加法过程中我们很容易想到没那么简单直接加是肯定会爆的, 那么难道我们还要塞一段大数加法吗?

要是这么想, 那也太烦了, 因为个位数乘以第一个数本身就是个大数. 那么为什么不和加法一样, 每一位乘以每一位呢? multiply

这样一来, 我们将乘法运算拆分为了10以内的乘法与三位数加法的组合

代码中由于去掉了临时变量 \(t\), 因此要先将 \(C\) 数组大小初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void multiply(vector<int> &A, vector<int> &B, vector<int> &C){
    for(int i = 0; i < A.size(); i++){
        for(int j = 0; j < B.size(); j++){  // 改进了一下, 去掉了临时变量
            C[i + j] += A[i] * B[j];  // 第几位表示的是10的几次幂(严谨点应该是10的几-2次幂), 因此只要下标和相同, 最后进的肯定是同一位
            C[i + j + 1] += C[i + j] / 10;  // 进位
            C[i + j] %= 10;  // 取余
        }
    }
}

// main函数
C.resize(A.size() + B.size(), 0);
multiply(A, B, C);
for(int i = C.size() - 1; i >= 0; i--) cout << C[i];

2.4 除法

来到除法, 我们得改一下题目只要求输出整数部分, 且除数为正常整数(其实还可以顺手把余数输出)

和其他三种运算不同, 我们计算除法是从左到右计算的, 还是画一幅竖式辅助思考: division

在例子中, 我们从被除数的 \(0\) 号位开始逐位往右除, 而结果也是从 \(0\) 号位开始逐位往右添加, 那么这样看来, 我们就不需要像之前一样将字符串反转存入数组再将结果反转读出了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> A, C;
int B;  // 因为明确除数是可以存的整数了

void divide(vector<int> &A, int B, vector<int> &C){
    unsigned long long t = 0;
    for(int i=0; i < A.size(); i++){
        t = t * 10 + A[i];
        C.push_back(t / B);
        t = t % B;
    }
}

// main函数
string a;
cin >> a >> B;
for(int i=0; i < a.size(); i++) A.push_back(a[i] - '0');

divide(A, B, C);

最后输出的时候和减法一样也要删除前导 \(0\)

1
2
while(C.size() > 1 && C.front() == 0) C.erase(C.begin());
for(int i = 0; i < C.size(); i++) cout << C[i];  // 注意从前往后输出

此时其实还应该检查一下若结果就是 \(0\), 会不会出问题