12.模拟与高精度

发表于 更新于 分类于 ，

模拟与高精度

通过编程模拟生活中的活动、现象，是解决各种问题的基础。很多问题并不需要特定的算法去解决，往往有效利用各种数据类型，根据问题的背景建模为数据的表达，按部就班地操作，就可以得到答案。

超出 long long (\(2^64\)) 范围的数字的加减乘除就是一类典型的模拟，称为高精度问题。

基本的模拟

例：机器人的指令

数轴原点有一个机器人。该机器人将执行一系列指令，你的任务是预测所有指令执行完毕之后它的位置。

  • LEFT：往左移动一个单位
  • RIGHT: 往右移动一个单位
  • SAME AS i: 和第i 条执行相同的动作。输入保证i 是一个正整数，且不超过之前执行指令数

输入第一行为数据组数\(T (T \leq 100)\)。每组数据第一行为整数\(n (1\leq n\leq 100)\)，即指令条数。以下每行一条指令。指令按照输入顺序编号为1~n。

对于每组数据，输出机器人的最终位置。每处理完一组数据，机器人应复位到数轴原点。

输入

1
2
3
4
5
6
7
8
9
10
11
2
3
LEFT
RIGHT
SAME AS 2
5
LEFT
SAME AS 1
SAME AS 2
SAME AS 1
SAME AS 4

输出

1
2
1
-5

记录操作不一定要记单词，能区分它们就行，然后按照要求移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
char op[111], buf[111];
int main() {
    int t, n, x;
    for(scanf("%d", &t); t --; ) {
        scanf("%d", &n);
        x = 0;  // 多组测试数据，每次都要初始化
        for(int i = 0; i < n; i ++) {
            scanf("%s", buf);
            if(buf[0] == 'L') op[i] = 'L';
            else if(buf[0] == 'R') op[i] = 'R';
            else {
                scanf("%s", buf);
                int ith;
                scanf("%d", &ith);
                op[i] = op[ith - 1];
            }
            x += op[i] == 'L' ? -1 : 1;
        }
        printf("%d\n", x);
    }
    return 0;
}

高精度

大整数加法

模拟小学学习的竖式，两个数组表示两个加数，另一个数组表示相加之和，数组每一项代表一位，下标0对应个位，1对应十位……

通常以字符串形式输入，然后处理为数字。

知识点：字符的ASCII码（char存储）本身也是数字，只不过char是8位二进制，只能表示-128~127，只要在此范围内，把它当数字去计算是可以的。但要注意，'1' 的编码是49，要想让字符'1'成为数字'1'，可以由'1' - '0' 计算偏移量。

以下代码仅供参考，具体实现可以有不同风格，选择自己易理解易记忆的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<string.h>
#include<algorithm>
char a[511], b[511], c[511];
int main() {
    scanf("%s%s", a, b);
    int alen = strlen(a), blen = strlen(b), clen = 0;
    // 读入的时候 [0] 存的高位，翻转过来，让[0]存个位，方便a和b对齐
    std::reverse(a, a + alen);
    std::reverse(b, b + blen);
    for(clen = 0; clen < alen || clen < blen; clen ++) {
        // 字符ASCII码处理为数字
        c[clen] = (clen < alen ? a[clen] - '0' : 0) + (clen < blen ? b[clen] - '0' : 0);
        if(clen > 0) {
            c[clen] += c[clen - 1] / 10;
            c[clen - 1] %= 10;
        }
    }
    if(c[clen - 1] > 9) {
        c[clen - 1] %= 10;
        c[clen ++] ++;
        
    }
    for(int i = clen - 1; i >= 0; i --) {
        printf("%d", c[i]); // 这里c存的是“数字”`0,1,2`，而不是字符`'0','1','2'`，所以用%d输出
    }
    printf("\n");
    return 0;
}

大整数乘法

比加法稍复杂一点，仍然是小学竖式的模拟。可以简化处理的是，可以把进位放在各位相乘之后再统一处理，每个位就只需要处理一次进位了。

以下代码仅供参考，具体实现可以有不同风格，选择自己易理解易记忆的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<string.h>
#include<algorithm>
char a[2111], b[2111];
// 进位累加过程中可能 char 的128存不下，存结果用int
// 两数相乘结果的位数不小于两数位数之和，数组开大一倍
int c[4111];
int main() {
    scanf("%s%s", a, b);
    int alen = strlen(a), blen = strlen(b), clen = 0;
    std::reverse(a, a + alen);
    std::reverse(b, b + blen);
    memset(c, 0, sizeof(c));    // 初始化 c 数组，确保全为 0
    for(int i = 0; i < alen; i ++) {
        for(int j = 0; j < blen; j ++) {
            // 比如 80 * 900，其 8（下标1） * 9（下标2） = 72 应该落在 72000（下标3）上
            // 进位可结束之后再统一处理
            c[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }
    for(; clen < alen + blen + 5; clen ++) {
        c[clen + 1] += c[clen] / 10;
        c[clen] %= 10;
    }
    // 去掉高位前导 0，且即使c是0也至少有 1 位数
    for(; clen > 1 && c[clen - 1] == 0; clen --);    
    for(int i = clen - 1; i >= 0; i --) {
        printf("%d", c[i]);
    }
    printf("\n");
    return 0;
}