【GESP】C++三级模拟题 luogu-B3849 [GESP样题 三级] 进制转换
GESP三级模拟样题,字符串和进制转换相关,难度★★✮☆☆。
luogu-B3849 [GESP样题 三级] 进制转换
题目要求
题目描述
小美刚刚学习了十六进制,她觉得很有趣,想到是不是还有更大的进制呢?在十六进制中,用
A
表示 $10$、F
表示 $15$。如果扩展到用Z
表示 $35$,岂不是可以表示 $36$ 进制数了嘛!所以,你需要帮助她写一个程序,完成十进制转 $R$ 进制($2\le R\le 36$)的工作。
输入格式
输入两行,第一行包含一个正整数 $N$,第二行包含一个正整数 $R$,保证 $1\le N\le 10^6$。
输出格式
输出一行,为 $N$ 的 $R$ 进制表示。
输入输出样例 #1
输入 #1
1
2
123
25
输出 #1
1
4N
题目分析
解题思路
十进制转换为其他进制的基本思路是:
- 不断用目标进制R除十进制数N,得到余数
- 余数即为当前位的值,商作为新的N继续除以R
- 所有余数从后往前拼接即为结果
- 如果余数大于9,则用A-Z表示(A表示10,B表示11,以此类推)
例如,将123转换为25进制:
- 123 ÷ 25 = 4 余 23(用N表示)
- 4 ÷ 25 = 0 余 4
- 从后往前拼接:4N
因此,本题的解题思路可以分为以下几个步骤:
- 读取输入数据:
- 读取十进制数N
- 读取目标进制R(2≤R≤36)
- 进制转换处理:
- 循环处理N,直到N为0:
- 计算当前位的值:N对R取余
- 更新N:N除以R取整
- 根据余数确定当前位的表示:
- 余数小于等于9时,用数字表示
- 余数大于9时,用字母A-Z表示(10用A,35用Z)
- 将当前位添加到结果字符串的开头
- 循环处理N,直到N为0:
复杂度分析:
- 时间复杂度:$O(\log_R N)$,需要进行N除以R的次数
- 空间复杂度:$O(\log_R N)$,需要存储结果字符串
示例代码
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
#include <iostream>
#include <string>
int main() {
// 声明变量存储十进制数N和目标进制R
int N, R;
std::cin >> N >> R;
// 用字符串存储结果
std::string result = "";
do {
// 获取当前位的值
int cur = N % R;
// 更新N为商
N /= R;
char c;
// 如果当前位大于9,需要用字母A-Z表示
if (cur > 9) {
c = char(cur - 10 + (int)'A');
} else {
// 否则用数字0-9表示
c = char(cur + '0');
}
// 将当前位添加到结果字符串的开头
result = c + result;
} while (N != 0); // 当N不为0时继续循环
// 输出结果
std::cout << result;
return 0;
}
所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页
“luogu-”系列题目已加入洛谷Java、C++初学团队,作业清单,可在线评测,团队名额有限,欢迎加入。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
本文由作者按照 CC BY 4.0 进行授权