PAT乙级1074 || 宇宙无敌加法器（详解，C/C++示例，测试点分析）

Posted on In

宇宙无敌加法器

题目描述

地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个 PAT 星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是 7 进制数、第 2 位是 2 进制数、第 3 位是 5 进制数、第 4 位是 10 进制数，等等。每一位的进制 d 或者是 0（表示十进制）、或者是 [2，9] 区间内的整数。理论上这个进制表应该包含无穷多位数字，但从实际应用出发，PAT 星人通常只需要记住前 20 位就够用了，以后各位默认为 10 进制。

在这样的数字系统中，即使是简单的加法运算也变得不简单。例如对应进制表“0527”，该如何计算“6203 + 415”呢？我们得首先计算最低位：3 + 5 = 8；因为最低位是 7 进制的，所以我们得到 1 和 1 个进位。第 2 位是：0 + 1 + 1（进位）= 2；因为此位是 2 进制的，所以我们得到 0 和 1 个进位。第 3 位是：2 + 4 + 1（进位）= 7；因为此位是 5 进制的，所以我们得到 2 和 1 个进位。第 4 位是：6 + 1（进位）= 7；因为此位是 10 进制的，所以我们就得到 7。最后我们得到：6203 + 415 = 7201。

输入格式

输入首先在第一行给出一个 N 位的进制表（0 < N ≤ 20），以回车结束。 随后两行，每行给出一个不超过 N 位的非负的 PAT 数。

输出格式

在一行中输出两个 PAT 数之和。

输入样例1

1
2
3
30527
06203
415

输出样例1

1
7201

输入样例2

1
2
3
23456
00000
12347

输出样例2

1
100001

问题解决

解题思想

这道题花费了我很长很长时间，虽说没什么难度，但是一些细节的处理麻烦深深地折磨了我。

首先要注意的是进制表中十进制是用0表示的，这个要做特殊处理，转换成数字后要加上10，否则会有除以0的危险；其次，当进位超过进制表所给最高位数时，要直接输出最高位进位（默认十进制）；还有最终结果前面的0都要去掉；当结果为0时要只输出一个0。

坑点提醒

测试点1 3

进位超过进制表所给最高位数，要直接输出最高位进位（注意看自己的代码能否正确处理测试样例2）

测试点5

结果为0时只输出一个0，注意下面的测试样例能否正确处理

1
2
3
4
5
6
input:
1234
00
00
output:
0

代码示例（C/C++）

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
void strrever(char str[]);
int main() {
    char str[21], a[21], b[21], re[22];
    cin >> str >> a >> b;
    strrever(str);
    int lena = strlen(a), lenb = strlen(b);
    int i, j, k, c = 0;  //进位，初始化为0
    for(i = 0; i < strlen(str); i++) { //0代表十进制
        if(str[i] == '0') {
            str[i] = 10 + '0';
        }
    }
    for(i = lena - 1, j = lenb - 1, k = 0; !(c == 0 &&(j < 0 || i < 0)); k++) {
        int sum;
        if(i >= 0 && j >= 0) {
            sum = a[i] + b[j] + c - 2 * '0';
            i--;
            j--;
        }
        else if(c != 0 && j < 0 && i < 0) {
             re[k++] = c + '0';   //very important
             break;
        }
        else if( i < 0) {
            sum = b[j] + c - '0';
            j--;
        }
        else if( j < 0) {
            sum = a[i] + c - '0';
            i--;
        }
        re[k] = sum % (str[k] - '0') + '0';
        c = sum / (str[k] - '0');
    }
    re[k] = '\0';   //very important
    int flag = 1;
    if(i >= 0) {    //a比b长，a还没有加完
        for(int t = 0; t <= i; t++) {
            if(flag) {
                if(a[t] != '0') {
                    printf("%c", a[t]);
                    flag = 0;
                }
            }
            else {
                printf("%c", a[t]);
            }
        }
    }
    else if(j >= 0) {   //b比a长，b还没加完
        for(int t = 0; t <= j; t++) {
            if(flag) {
                if(b[t] != '0') {
                    printf("%c", b[t]);
                    flag = 0;
                }
            }
            else {
                printf("%c", b[t]);
            }
        }
    }
    strrever(re);
    if(flag == 0) { //已输出一部分
        cout << re;
    }
    else {  //还没有输出，re结果中前面的0要去掉
        for(i = 0; i < strlen(re); i++) {
            if(flag) {
                if(re[i] != '0') {
                    printf("%c", re[i]);
                    flag = 0;
                }
            }
            else {
                printf("%c", re[i]);
            }
        }
    }
    if(flag) {  //没有输出时最后输出一个0
        printf("0");
    }
    return 0;
}
//逆置字符串
void strrever(char str[]) {
    char tmp;
    int len = strlen(str);
    for(int i = 0; i < len / 2; i++) {
        tmp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = tmp;
    }
}

题目来源：PAT乙级1074
作者：CHEN, Yue
单位：浙江大学

稀罕作者