中 · 数制
进制转换
你已经会转二进制了。换成其他进制,变的只有那个「基」—— 以及超过 10 之后,数字字符就不够用了。
一句话答案反复取 n % base 作为下一位、同时把 n 除以 base，最后把得到的位倒序打印 —— 大于 9 的位用 A 到 F，n 为 0 时输出 0。
题目
输入: 一行两个整数:n(0 ≤ n ≤ 1,000,000)和 base(2 ≤ base ≤ 16)。
输出: n 在该进制下的写法。大于 9 的数字用大写字母 A–F。若 n 为 0,输出 0。
样例:
| 输入 | 输出 |
|---|---|
255 16 | FF |
10 2 | 1010 |
0 2 | 0 |
余数出来是反的。10 转二进制依次得到余数 0、1、0、1 —— 正好是答案倒着念。所以先收集,再倒序输出。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 从你已经写过的二进制开始
二进制题里你做的是 n % 2 和 n / 2。把 2 换成 base,算法一个字都不用改 —— 因为它本来就不关心基是多少。这就是「通用解」的意义。
提示 2 — 大于 9 的数字需要换算
余数是 0–15 的数字,但你要存的是字符。0–9 用 '0' + r,10–15 用 'A' + (r - 10)。一个三目就能兼顾:r < 10 ? '0' + r : 'A' + r - 10。
提示 3 — 0 是那个让循环失效的情况
while (n > 0) 在 n 为 0 时一次都不执行,于是什么都没收集,你会打印一个空行。在循环前单独处理:n == 0 就直接输出 0 并结束。每一个「把数拆成数字」的例程都会在这上面栽一次。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n, base;
cin >> n >> base;
if (n == 0) {
cout << 0 << endl;
return 0;
}
char digit[64];
int k = 0;
while (n > 0) {
int r = n % base;
digit[k] = (r < 10) ? ('0' + r) : ('A' + r - 10);
k++;
n = n / base;
}
for (int i = k - 1; i >= 0; i--) cout << digit[i];
cout << endl;
return 0;
}反复除法的余数,倒着读,就是各位数字。这一句话同时解释了二进制、八进制、十六进制和所有位置计数法 —— 它们的区别只是数缩小的快慢。反方向(把某进制的字符串转回整数)是同一个循环倒过来写:n = n * base + digit,而这正是 stoi 和 cin >> 内部做的事。下一题,一个从头到尾不需要比较的排序:计数排序。
深度解析
为什么这样做对
反复除法的余数,倒着读,就是各位数字。这一句话同时解释了所有位置计数法。
代价
O(log_基 n) 次除法。基越大越快:十亿这个数,二进制要 30 次,十六进制只要 8 次。
常见错法
- 忘记倒序:余数出来本来就是反的。10 转二进制依次得到 0、1、0、1 —— 正着输出就是
0101。 - 漏掉
n == 0:while (n > 0)一次都不跑,你会打印一个空行。而 0 在任何进制下都是0。
下一步
一个从头到尾不比较任何两个数的排序:计数排序。
记住这两句
- 余数倒着读就是各位数字 —— 二、八、十六进制都是这一句。
- 0 要单独处理,否则打印空行。
🐞 这段是错的 —— 点开,亲手让它挂一次
余数按收集顺序直接输出 —— 数字是反的
#include <iostream>
using namespace std;
int main() {
int n, base;
cin >> n >> base;
if (n == 0) {
cout << 0 << endl;
return 0;
}
char digit[64];
int k = 0;
while (n > 0) {
int r = n % base;
digit[k] = (r < 10) ? ('0' + r) : ('A' + r - 10);
k++;
n = n / base;
}
for (int i = 0; i < k; i++) cout << digit[i];
cout << endl;
return 0;
}