GESP 题解库 / 3 级题解 / [GESP样题 三级] 进制转换 · 第 24 / 28 题
GESP样题 三级 · B3849 · 简单

进制转换

把十进制数 N 转换成 R 进制(2 ≤ R ≤ 36),10 以上用 A ~ Z 表示。

📊
N ≤ 10⁶
数值范围
🔢
2 ≤ R ≤ 36
目标进制
⚡
O(log_R N)
时间复杂度
🎯
除 R 取余
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

十六进制中 A 表示 10、F 表示 15。如果扩展到用 Z 表示 35,就可以表示 36 进制数了。请完成十进制转 R 进制(2 ≤ R ≤ 36)的工作。

例如输入 123 和 25,输出 4N。

💡
人话翻译:反复做"除以 R 取余数",把余数从后往前拼起来就是答案。余数 0 ~ 9 用数字字符表示,10 ~ 35 用 A ~ Z 表示。

🔍 关键词提取

除基取余逆序拼接字符映射表边界处理

已知条件

项目说明
输入第一行 N,第二行 R
输出N 的 R 进制表示
数值范围1 ≤ N ≤ 10⁶
进制范围2 ≤ R ≤ 36
字符映射0 ~ 9 用数字,10 ~ 35 用 A ~ Z

需要解决的问题

02
思维导图
整理解题思路的全貌
🔄 除 R 取余再倒序
📥 读入
读 N 和 R
R 在 2 ~ 36
N 可达 10⁶
用 int 就够
🔁 除法循环
N 除以 R 得商和余数
余数当"低位"先得到
商作为下一轮的被除数
直到商为 0
🔤 字符映射
建表 "0-9A-Z"
余数当数组下标
要 .c_str() 或直接整串
10 → A、35 → Z
🔚 输出
余数序列要倒序
可以边算边往前面插
或存数组后逆序输出
N = 0 特判
03
样例手算推导
样例 123 转 25 进制

🧮 123 转 25 进制,得到 4N

反复做"除 25 取余",把余数倒过来拼。

1
第 1 轮

123 ÷ 25 = 4 余 23

23 对应的字符是 N(A = 10、B = 11 … N = 23)

商 4 作为下一轮的被除数

得到最低位 N

2
第 2 轮

4 ÷ 25 = 0 余 4

4 对应的字符是 4

商为 0,循环结束

得到次低位 4

3
倒序拼接

余数出现顺序是 23、4

倒过来就是 4、23

对应字符 4 和 N

✅ 结果 4N

轮次被除数÷ 25 的商余数余数对应的字符
1123423N
24044

倒序拼接:4 + N = 4N ✓(验算:4 × 25 + 23 = 100 + 23 = 123)

🧮 字符映射表怎么建

36 进制需要 36 个字符,正好用 "0123456789ABC…Z" 这个长度 36 的串。

余数对应字符说明
0 ~ 90 ~ 9直接用数字字符
10A十进制的 10 在十六进制里就是 A
15F十六进制最大值
23N本题样例用到的
35Z36 进制的最大值
🔑
为什么把字符表写成一个字符串最方便?因为 "0123456789ABC...Z"[余数] 正好就是该余数对应的字符,一个下标运算解决映射,不用写任何 if-else。
04
解法对比
字符表下标 vs 分支判断

⚔️ 解法对比

🟢 字符表取下标(推荐) 推荐

准备 36 个字符的字符串,用余数当下标

  • 时间 O(log_R N)
  • 映射只需一次下标
  • 扩展到 36 进制毫无压力
  • 代码 12 行
💡
循环次数:N ≤ 10⁶、R ≥ 2 时最多约 20 次除法,所以运算量极小。

🟠 用 if-else 判断余数范围

余数小于 10 输出数字,否则输出对应字母

  • 多一个分支但也不难
  • 只支持到 36 进制
  • 可读性尚可
  • 两者都行
⚠️
对比:分支写法要多写 if (r < 10) 这样的判断,字符表写法更统一,也不容易在边界(余数 = 9 或 10)出错。

📈 性能对比

方案代码量边界风险
字符表约 12 行低
if 分支约 15 行中
05
算法流程图
除法循环 + 逆序输出
开始读入 N、R;建字符表 "0-9A-Z"N 是否等于 0?是 ✓输出 0 并结束否 ✗继续除法N > 0 时循环余数 = N % R;N = N / R把字符表[余数] 存起来(作为低位)倒序输出所有存下的字符结束N 还大于 0 → 继续除
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔄 进制转换器

输入两个整数:N 和 R(用空格分隔),程序会展示除基取余的每一步。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, R;
    scanf("%d %d", &N, &R);

    // 字符表:余数 0~35 直接当下标查
    const string DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    if (N == 0) { printf("0\n"); return 0; }   // 特判 0

    string ans = "";
    while (N > 0) {
        int r = N % R;
        ans = DIG[r] + ans;    // 关键:插到最前面,实现"逆序"
        N /= R;
    }

    printf("%s\n", ans.c_str());
    return 0;
}
🔑
ans = DIG[r] + ans 这一行为什么能实现逆序?每算出一个新余数(它是更高的一位),就把它拼到当前字符串的前面。这样一轮轮下来,最终顺序自然就对了,不用再单独做一次 reverse。

📖 关键几行怎么看

代码作用为什么这样写
const string DIG = "0-9A-Z"字符映射表一共 36 个字符,余数直接当下标
if (N == 0)特判 00 的循环一次都不会执行,会输出空串,必须单独处理
ans = DIG[r] + ans逆序拼接新余数是高位,插到前面
N /= R更新被除数整数除法自动取整
⚠️
三个坑:① 忘了特判 N = 0,会输出空行;② 用 ans += DIG[r] 顺序拼接,得到的是倒序结果(低位在前),必须反转;③ 字符表只写到 F(只支持 16 进制),本题要求支持到 36 进制,必须写到 Z。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
123 254N题面样例
10 21010转二进制
255 16FF转十六进制
1 21最小输入
1000000 36LFLS最大规模 + 最大进制
35 36Z正好用到字符表最后一个
✅
自查清单:① 字符表够 36 个吗?② 拼接顺序对吗(新余数插前面)?③ 特判 0 了吗?

🚨 易错点清单

⚠️
忘了特判 N = 0:循环体一次都不执行,会输出空字符串。本题 N ≥ 1 所以不影响,但规范写法要加上。
⚠️
顺序拼接:ans += DIG[r] 得到的是低位在前,必须写 ans = DIG[r] + ans 或最后 reverse。
⚠️
字符表不全:只写到 F 就只能处理 16 进制,36 进制需要完整的 0-9A-Z。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(log_R N)
空间复杂度
O(log_R N)
N 最大
10⁶
循环次数
最多约 20

时间怎么算的?

空间都用在哪?

需要存下结果字符串,长度就是转换后的位数 log_R N。

✅ 最多 20 次循环,任何写法都瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 十进制转任意进制(2 ~ 36)的标准模板
string toBase(int n, int base) {
    const string DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (n == 0) return "0";
    string ans;
    while (n > 0) { ans = DIG[n % base] + ans; n /= base; }
    return ans;
}

// 任意进制转十进制
int toDecimal(const string &s, int base) {
    const string DIG = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int r = 0;
    for (char c : s) r = r * base + (int)DIG.find(c);
    return r;
}

// 用 <bitset> 或 printf 直接输出(仅限 2/8/16 进制)
// printf("%o", n);         八进制
// printf("%X", n);         十六进制

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
除基取余反复除 R 记录余数所有进制转换题
字符表映射用值当下标查字符编码、映射、查表类问题
插前面实现逆序ans = c + ans需要逆序输出的场景
🌟
思考题:如果要反过来——把 R 进制字符串转成十进制,该怎么写?(提示:从左到右累乘:result = result × R + 当前位的值,这是上面 toDecimal 的思路,比逐位加幂次更简洁。)