欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT乙级真题1074 || 宇宙无敌加法器(详解,C/C++示例,测试点分析)

程序员文章站 2024-03-23 21:23:52
...

PAT乙级真题1074 || 宇宙无敌加法器(详解,C/C++示例,测试点分析)
【欢迎关注微信公众号:计算机黑科学大全,对话框回复:PAT乙级真题】获取全部真题详解及代码示例
个人博客地址:https://mzwang.top

宇宙无敌加法器

题目描述:

地球人习惯使用十进制数,并且默认一个数字的每一位都是十进制的。而在 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:

30527
06203
415

输出样例1:

7201

输入样例2:

23456
00000
12347

输出样例2:

100001

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

问题解决:

解题思想

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

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

坑点提醒

测试点1 3

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

测试点5

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

input:
1234
00
00
output:
0

代码示例(C/C++)

小提示:请将以下代码保存为.cpp格式(C++程序)左右滑动代码以查看完整代码(复制本文链接到电脑端浏览效果更佳)

#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 || 宇宙无敌加法器(详解,C/C++示例,测试点分析)

相关标签: PAT乙级真题详解