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;
}
}
上一篇: 最新面试问题
下一篇: 对于OC对象,引用以及isa的理解
推荐阅读
-
16 C++知识点之do-while语句
-
PAT 甲级 1030 Travel Plan (30 分)(dijstra,较简单,但要注意是从0到n-1)
-
C语言链表的输入输出
-
PAT甲级真题 1001 A+B Format
-
PAT乙级真题1079 || 延迟的回文数(详解,C/C++示例,测试点分析)
-
类初始化与实例初始化过程分析
-
PAT乙级真题1074 || 宇宙无敌加法器(详解,C/C++示例,测试点分析)
-
PAT乙级真题1077 || 互评成绩计算(详解,C/C++示例,测试点分析)
-
C语言编程学习:制作掷骰子小游戏!超适合新手的练手项目!
-
[C++]读取txt文件,存入进二维数组中(Xcode)