把 N 个 K 进制数(2 ≤ K ≤ 16)分别转换成十进制输出。
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。
Horner 法则字符转数值从左到右累乘避免幂运算
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;随后 N 行每行 K 和 K 进制数 |
| 输出 | N 行,每行对应的十进制数 |
| 数据范围 | N ≤ 1000,2 ≤ K ≤ 16 |
| 位数 | 每个数不超过 9 位 |
| 字符集 | 数字与大写字母,不以 0 开头 |
res = res * K + digit'0'~'9' → 0 ~ 9;'A'~'F' → 10 ~ 15用"从左到右累乘"的方法,每读一位就乘 8 再加。
| 读入的位 | 字符值 | 计算过程 | res |
|---|---|---|---|
| 1 | 1 | res = 0 × 8 + 1 | 1 |
| 3 | 3 | res = 1 × 8 + 3 | 11 |
| 6 | 6 | res = 11 × 8 + 6 | 94 |
| 2 | 2 | res = 94 × 8 + 2 | 754 |
位权法:1×8³ + 3×8² + 6×8¹ + 2×8⁰
= 512 + 192 + 48 + 2 = 754
累乘法每步的结果:1 → 11 → 94 → 754
两者结果完全一致
✅ 两种方法等价
位权法要先算出 8³、8²、8¹ 等幂次
或者从右往左处理
累乘法只用一个变量、一趟从左到右
代码更短,也不容易出错
✅ 推荐累乘法
八进制 1362 = 754 ✓
注意 F 要转成数值 15。
| 读入的位 | 字符值 | 计算过程 | res |
|---|---|---|---|
| 3 | 3 | res = 0 × 16 + 3 | 3 |
| F | 15 | res = 3 × 16 + 15 | 63 |
| 0 | 0 | res = 63 × 16 + 0 | 1008 |
十六进制 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 存结果会溢出,这是本题最容易失分的地方。res = res * K + digit,一趟扫描
(...((d₁ × K + d₂) × K + d₃) × K + ...) 展开后恰好等于 d₁K^(n-1) + d₂K^(n-2) + ...,与位权法完全等价。从最低位开始,每位乘 K 的对应次幂再累加
pow(K, i) 会引入浮点误差,对 10¹⁰ 量级的整数可能算错最后几位,整数题里应避免用 pow。| 方案 | 代码量 | 风险 |
|---|---|---|
| Horner 累乘 | 约 5 行 | 无 |
| 位权法 + pow | 约 10 行 | 浮点误差 |
每行输入"K 和 K 进制数"(空格分隔),程序会展示逐位累乘过程。
点按钮开始 →
#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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
8 1362 | 754 | 题面样例 1 |
16 3F0 | 1008 | 题面样例 1 |
2 11011 | 27 | 题面样例 2 |
10 123456789 | 123456789 | 十进制本身(验证算法无损) |
16 FFFFFFFF | 4294967295 | 8 位十六进制,超过 int 上限 |
16 FFFFFFFFF | 68719476735 | 9 位十六进制,必须用 long long |
c - 'A' 会得到 5。pow(16, 8) 返回浮点数,大数时可能丢失精度。只需要一个累加变量。
✅ 运算量不到 1 万次,瞬间完成。这题考的是 Horner 累乘技巧和对数据类型的选择。
// 任意进制转十进制(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 法则 | 从左到右累乘 | 所有进制转换题 |
| 字符与数值互转 | 数字/字母统一映射 | 进制、编码、密码类题目 |
| 数据类型选择 | 预估最大值再选类型 | 所有涉及乘加累加的题目 |