数的进制转换
编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。
这里有 62 个不同数位 {0−9,A−Z,a−z}。
输入格式
第一行输入一个整数，代表接下来的行数。
接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。
输入进制和输出进制都在 2 到 62 的范围之内。
（在十进制下）A=10，B=11，…，Z=35，a=36，b=37，…，z=61 (0−9 仍然表示 0−9)。
输出格式
对于每一组进制转换，程序的输出都由三行构成。
第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。
第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。
第三行为空白行。
同一行内数字用空格隔开。
输入样例：
1
2
3
4
5
|
8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
|
输出样例：
1
2
3
4
5
6
7
8
9
10
11
|
62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001
10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A
35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05
|
分析
- 使用字符串表示输入数字
- 将输入字符串转换为整型数组，每个元素表示一个数位，得到一个 a 进制的高精度数
- 遍历高精度数，每次对当前数位除以 b， 余数（当前位），商（继续参与下一轮）
- 收集余数，每次的余数加入结果（低位 → 高位）
- 反转结果数组，再映射成字符串
时空复杂度
C++代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <iostream>
#include <vector>
#include <algorithm>
std::string transform(int a, int b, std::string& a_line)
{
// 字符串 -> a 进制数字数组
std::vector<int> number;
for (char c : a_line)
{
if (c >= '0' && c <= '9')
number.push_back(c - '0');
else if (c >= 'A' && c <= 'Z')
number.push_back(c - 'A' + 10);
else if (c >= 'a' && c <= 'z')
number.push_back(c - 'a' + 36);
}
std::reverse(number.begin(), number.end()); // 低位在前，便于做高精度除法
std::vector<int> res;
// 循环：高精度数不断 ÷ b
while (number.size())
{
int t = 0; // 当前余数
for (int i = number.size() - 1; i >= 0; -- i)
{
number[i] = number[i] + t * a; // 当前位 + 上一位余数
t = number[i] % b; // 更新余数
number[i] /= b; // 更新商（保留用于下一轮）
}
res.push_back(t); // 收集余数（从低位到高位）
// 去掉前导 0（避免无效计算）
while (number.size() && number.back() == 0)
number.pop_back();
}
std::reverse(res.begin(), res.end()); // 反转得到高位在前
// 转回字符
std::string b_line;
for (int x : res)
{
if (x >= 0 && x <= 9)
b_line += char(x + '0');
else if (x >= 10 && x <= 35)
b_line += char(x - 10 + 'A');
else if (x >= 36 && x <= 61)
b_line += char(x - 36 + 'a');
}
return b_line;
}
int main()
{
int n;
std::cin >> n;
while (n -- )
{
int a, b;
std::string a_line, b_line;
std::cin >> a >> b >> a_line;
b_line = transform(a, b, a_line);
std::cout << a << ' ' << a_line << std::endl;
std::cout << b << ' ' << b_line << std::endl;
std::cout << std::endl;
}
return 0;
}
|
