【GESP】C++四级真题 luogu-B3869 [GESP202309 四级] 进制转换
GESP C++四级2023年9月真题，函数、进制转换等应用，难度⭐⭐★☆☆。本题在洛谷评定为普及-。
luogu-B3869 [GESP202309 四级] 进制转换
题目要求
题目描述
$N$ 进制数指的是逢 $N$ 进一的计数制。例如，人们日常生活中大多使用十进制计数，而计算机底层则一般使用二进制。除此之外，八进制和十六进制在一些场合也是常用的计数制（十六进制中，一般使用字母 A 至 F 表示十至十五；本题中，十一进制到十五进制也是类似的）。
在本题中，我们将给出 $N$ 个不同进制的数。你需要分别把它们转换成十进制数。
输入格式
输入的第一行为一个十进制表示的整数 $N$。接下来 $N$ 行，每行一个整数 $K$，随后是一个空格，紧接着是一个 $K$ 进制数，表示需要转换的数。保证所有 $K$ 进制数均由数字和大写字母组成，且不以 $0$ 开头。保证 $K$ 进制数合法。
保证 $N \le 1000$；保证 $2 \le K \le 16$。
保证所有 $K$ 进制数的位数不超过 $9$。
输出格式
输出 $N$ 行，每一个十进制数，表示对应 $K$ 进制数的十进制数值。
输入输出样例 #1
输入 #1
1
2
3
2
8 1362
16 3F0
输出 #1
1
2
754
1008
输入输出样例 #2
输入 #2
1
2
3
2
2 11011
10 123456789
输出 #2
1
2
27
123456789
说明/提示
对于任意一个 $L$ 位 $K$ 进制数，假设其最右边的数位为第 $0$ 位，最左边的数位为第 $L-1$ 位，我们只需要将其第 $i$ 位的数码乘以权值 $K^i$，再将每位的结果相加，即可得到原 $K$ 进制数对应的十进制数。下面是两个例子：
八进制数
1362对应的十进制数为：$1×8^3+3×8^2+6×8^1+2×8^0=754$；十六进制数
3F0对应的十进制数为：$3×16^2+15×16^1+0×16^0=1008$。
题目分析
本题主要考察了进制转换和字符串处理的能力。解题思路如下：
核心思路
题目要求将不同进制的数转换为十进制数。对于任意一个K进制数，我们可以：
- 从右向左遍历每一位数字
- 将每一位的数值乘以对应的权重(K的幂次)
- 将所有位的结果相加得到最终的十进制数
实现要点
- 字符处理：使用字符串存储输入的$K$进制数，从右向左遍历每一位字符。
- 数字字符$(‘0’-‘9’)$需要减去$’0’$得到实际数值
- 字母字符$(‘A’-‘F’)$需要减去$’A’$后加$10$得到实际数值$(10-15)$
- 权重计算：按照位权展开公式计算每一位的权重。
- 第$i$位的权重为$K^i$ ($i$从右向左从$0$开始计数)
- 可以使用$pow$函数计算幂次
- 数据范围
- 进制$K$的范围是$[2,16]$
- 输入数字最多$9$位
- 需要使用$long\ long$类型存储结果防止溢出
算法复杂度
- 时间复杂度: $O(L)$，其中L为输入数字的位数
- 需要遍历输入数字的每一位
- 每位的计算(包括幂运算)是常数时间
- 空间复杂度: $O(1)$
- 只需要常数个变量存储中间结果和最终结果
示例代码
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
#include <iostream>
#include <string>
#include <cmath>
/**
* 将K进制字符串转换为十进制数
* @param s K进制字符串，仅包含数字0-9和大写字母A-F
* @param k 进制基数，范围2-16
* @return 转换后的十进制数
*/
long long trans_to_decimal(const std::string& s, const int k) {
// 存储转换后的十进制结果
long long decimal = 0;
// 从右向左遍历字符串的每一位
for (int i = s.length() - 1; i >= 0; i--) {
// 如果当前字符是数字
if (s[i] >= '0' && s[i] <= '9') {
// 将数字字符转换为对应的数值并乘以权重
decimal += (s[i] - '0') * std::pow(k, s.length() - i - 1);
} else {
// 如果是字母(A-F)，将其转换为对应的数值(10-15)并乘以权重
decimal += (s[i] - 'A' + 10) * pow(k, s.length() - i - 1);
}
}
return decimal;
}
int main() {
// 读取需要转换的数字个数
int n;
std::cin >> n;
// 处理每个输入的K进制数
for (int i = 0; i < n; i++) {
int k; // 进制基数
std::string s; // K进制字符串
std::cin >> k >> s;
// 输出转换后的十进制结果
std::cout << trans_to_decimal(s, k) << "\n";
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
