GESP 题解库 / 4 级题解 / [GESP202309 四级] 进制转换 · 第 19 / 25 题
GESP202309 四级 · B3869 · 简单

进制转换

把 N 个 K 进制数(2 ≤ K ≤ 16)分别转换成十进制输出。

📊
N ≤ 1000
数据组数
🔢
2 ≤ K ≤ 16
进制范围
⚡
O(位数)
时间复杂度
🎯
从左到右累乘(Horner)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

N 进制数逢 N 进一。十六进制中用字母 A ~ F 表示 10 ~ 15。

给出 N 个不同进制的数,请分别把它们转换成十进制数。每行输入一个整数 K 和一个 K 进制数(由数字和大写字母组成、不以 0 开头、保证合法)。

例:八进制 1362 = 1×8³ + 3×8² + 6×8¹ + 2×8⁰ = 754;十六进制 3F0 = 3×16² + 15×16 + 0 = 1008。

💡
人话翻译:把每一位数字乘上它的"位权"再相加。但更省事的写法是从左到右累乘:每读一位,就把当前结果乘 K 再加这一位的值。这样不用计算幂,一趟扫描就够。

🔍 关键词提取

Horner 法则字符转数值从左到右累乘避免幂运算

已知条件

项目说明
输入第一行 N;随后 N 行每行 K 和 K 进制数
输出N 行,每行对应的十进制数
数据范围N ≤ 1000,2 ≤ K ≤ 16
位数每个数不超过 9 位
字符集数字与大写字母,不以 0 开头

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 从左到右累乘
📥 读入
N ≤ 1000
每行 K 和字符串
位数 ≤ 9
结果用 long long
🔤 字符转数值
'0'~'9' → 0~9
'A'~'F' → 10~15
用 if 或查表
K ≤ 16 只需到 F
🧮 Horner 累乘
res = 0
每读一位:res = res*K + digit
一趟扫描完成
不需要算幂
⚠️ 易错点
用 int 导致溢出
字母转换漏掉 +10
误以为要算幂
读入格式(K 和数之间有空格)
03
样例手算推导
两个样例的逐位累乘

🧮 样例:八进制 1362 → 754

用"从左到右累乘"的方法,每读一位就乘 8 再加。

读入的位字符值计算过程res
11res = 0 × 8 + 11
33res = 1 × 8 + 311
66res = 11 × 8 + 694
22res = 94 × 8 + 2754
1
与"位权法"对照

位权法:1×8³ + 3×8² + 6×8¹ + 2×8⁰

= 512 + 192 + 48 + 2 = 754

累乘法每步的结果:1 → 11 → 94 → 754

两者结果完全一致

✅ 两种方法等价

2
为什么累乘法更好?

位权法要先算出 8³、8²、8¹ 等幂次

或者从右往左处理

累乘法只用一个变量、一趟从左到右

代码更短,也不容易出错

✅ 推荐累乘法

八进制 1362 = 754 ✓

🧮 样例:十六进制 3F0 → 1008

注意 F 要转成数值 15。

读入的位字符值计算过程res
33res = 0 × 16 + 33
F15res = 3 × 16 + 1563
00res = 63 × 16 + 01008

十六进制 3F0 = 1008 ✓

🔤 字符转数值对照

字符数值字符数值字符数值
'0'0'5'5'A'10
'1'1'6'6'B'11
'2'2'7'7'C'12
'3'3'8'8'D'13
'4'4'9'9'E'14
————'F'15
⚠️
一定要用 long long:9 位十六进制数的最大值是 16⁹ − 1 = 68719476735,远超 int 上限(约 2.1 × 10⁹)。用 int 存结果会溢出,这是本题最容易失分的地方。
04
解法对比
Horner 累乘 vs 位权法

⚔️ 解法对比

🟢 Horner 从左到右累乘(推荐) 推荐

res = res * K + digit,一趟扫描

  • 时间 O(位数)
  • 代码 5 行
  • 不需要算幂
  • 天然处理任意位数
💡
原理:把 (...((d₁ × K + d₂) × K + d₃) × K + ...) 展开后恰好等于 d₁K^(n-1) + d₂K^(n-2) + ...,与位权法完全等价。

🟠 位权法(从右往左)

从最低位开始,每位乘 K 的对应次幂再累加

  • 需要计算或维护幂 K^i
  • 要么写 pow()(浮点,不安全)
  • 要么自己维护一个递推的幂
  • 代码更长
⚠️
注意:用 pow(K, i) 会引入浮点误差,对 10¹⁰ 量级的整数可能算错最后几位,整数题里应避免用 pow。

📈 性能对比

方案代码量风险
Horner 累乘约 5 行无
位权法 + pow约 10 行浮点误差
05
算法流程图
逐位读字符并累乘
开始读入 N处理每组数据:读入 K 和字符串 sres = 0;依次取 s 中每个字符 c把 c 转成数值 d(数字→0~9,字母→10~15)res = res × K + d输出 res结束还有数据组 → 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 K 进制转十进制

每行输入"K 和 K 进制数"(空格分隔),程序会展示逐位累乘过程。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

// 字符 -> 数值:'0'~'9' 为 0~9,'A'~'F' 为 10~15
int charVal(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}

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

    while (n--) {
        int k;
        char s[20];
        scanf("%d %s", &k, s);       // K 和进制数之间用空格分隔

        long long res = 0;           // 必须用 long long
        for (int i = 0; s[i]; i++) {
            res = res * k + charVal(s[i]);   // Horner 累乘
        }

        printf("%lld\n", res);
    }
    return 0;
}
🔑
为什么 res * k + digit 能算出正确的位权?展开看:处理完前 m 位后,res 正好是这 m 位的值。再读一位时,前面所有位的"权重"都乘了 k(相当于左移一位),新位则加在最低位——这与手算"每位乘对应幂再相加"的结果完全一致,而且不需要显式计算幂。

📖 关键几行怎么看

代码作用为什么这样写
c - '0'数字字符转值'0' 的 ASCII 是 48
c - 'A' + 10字母转值A 对应 10
res = res * k + charVal(s[i])Horner 累乘一行完成"左移一位 + 加新位"
long long res类型选择9 位十六进制可达 6.9 × 10¹⁰,超过 int
⚠️
三个坑:① 用 int 存结果导致溢出;② 字母转换写成 c - 'A'(漏掉 +10);③ 输出格式用 %d 而不是 %lld。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
8 1362754题面样例 1
16 3F01008题面样例 1
2 1101127题面样例 2
10 123456789123456789十进制本身(验证算法无损)
16 FFFFFFFF42949672958 位十六进制,超过 int 上限
16 FFFFFFFFF687194767359 位十六进制,必须用 long long
✅
自查清单:① 结果用 long long 了吗?② 字母 +10 了吗?③ 输出用 %lld 了吗?

🚨 易错点清单

⚠️
用 int 存结果:9 位十六进制可达 6.87 × 10¹⁰,会溢出,必须用 long long。
⚠️
字母转换漏 +10:F 应该是 15,写成 c - 'A' 会得到 5。
⚠️
用 pow 算位权:pow(16, 8) 返回浮点数,大数时可能丢失精度。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N × 位数)
空间复杂度
O(1)
位数
≤ 9
N 最大
1000

时间怎么算的?

空间都用在哪?

只需要一个累加变量。

✅ 运算量不到 1 万次,瞬间完成。这题考的是 Horner 累乘技巧和对数据类型的选择。

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

🔗 常用技巧小抄

// 任意进制转十进制(Horner 法则)
long long toDecimal(const string &s, int base) {
    long long res = 0;
    for (char c : s) res = res * base + charVal(c);
    return res;
}

// 十进制转任意进制(除基取余,逆序拼接)
string fromDecimal(long long n, int base) {
    const string DIG = "0123456789ABCDEF";
    if (n == 0) return "0";
    string ans;
    while (n > 0) { ans = DIG[n % base] + ans; n /= base; }
    return ans;
}

// 溢出检查技巧:把 res * base + d 改写为判断形式
if (res > (LLONG_MAX - d) / base) { /* 会溢出 */ }

🌟 举一反三

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

能力点本题怎么用还能迁移到
Horner 法则从左到右累乘所有进制转换题
字符与数值互转数字/字母统一映射进制、编码、密码类题目
数据类型选择预估最大值再选类型所有涉及乘加累加的题目
🌟
思考题:如果题目要求"把十进制数转成 K 进制"(与本题方向相反),该怎么做?(提示:用除基取余——反复对 K 取余得到低位、除以 K 缩小,最后把余数序列倒序拼接。这正是 GESP 三级"进制转换"一题的解法,两者正好互为逆运算。)