写算法题的时候经常会碰到一些大数相关的问题，比如大数乘法、大数加法等等，乘法和加法的原理基本上都比较符合正常的思维模式，因为加法和乘法的原理相对清晰，模拟数学计算步骤可以方便地分离，并转换为代码。
相对于常见的加法和乘法，进制转换出现的频率低一些，但同样是一个十分值得探讨的问题，并且难度较之加法和乘法更高。
问题抽象
-
输入为 ($M$, $m$, $n$):
- $M$: $m$ 进制整数 $M$，用字符串类型
string 储存
- $m$: 大数基数 $m$
- $n$: 大数目的基数 $n$
-
输出为 N：
- $N$: $n$ 进制整数 $N$，用字符串类型
string 储存
数学原理
$m$ 进制转换成 $n$ 进制，通常采用的是「模 $n$ 取余法」，也称「辗转相除法」，一般数进制转换的方法：
进制转换方法
-
输入 $m$ 进制数 $M$ 作为除数，对目标进制基数 $n$ 求整数商得到商 $Q^1$ ，对基数 $n$ 取余得到余数 $R^1$，
-
若商 $Q^1$ 为 $0$，循环终止，否则，用商 $Q^1$ 作为除数，继续对基数 $n$ 求整数商得到商 $Q^2$，取余得到余数 $R^2$，
-
循环第2步，直到商 $Q^t$ 为 $0$，此时得到余数 $R^t$，
则余数序列 $R^tR^{t-1} \cdots R^1$ 为转换后的 $n$ 进制数 $N$。
一个简单的例子
如 $30 \to (11110)_2$
运算过程：
30 / 2 = 15, 0
15 / 2 = 7, 1
7 / 2 = 3, 1
3 / 2 = 1, 1
1 / 2 = 0, 1
可以想象，大数转换步骤同样如此。
问题只在于大数的整数除和取余比一般数字更复杂一些，这里将算法解释如下：
大数整数除及取余方法
-
设余数 $R=0$
-
由低位至高位，从大数中取数 $M^1$，用余数 $R$ 乘以进制基数 $m$ 后再加上数 $M^1$，得到数 $R \cdot m + M^1$，用该数对目标进制基数 $n$求整数商得到商 $Q^1$，对基数 $n$ 取余得到新的余数 $R$
-
循环第2步，直至取完大数所有位，得到商 $Q^t$ 和余数 $R$
则商序列 $Q^tQ^{t-1}\cdots Q^1$ 为整数商，$R$ 为余数。
一个稍微复杂的例子
eg. $(11110)_2 \to 30$
| 序号 |
当前位 |
运算 |
| 0 |
null |
null |
| 1 |
1 |
(0 * 2 + 1) / 10 = 0, 1 |
| 2 |
1 |
(1 * 2 + 1) / 10 = 0, 3 |
| 3 |
1 |
(3 * 2 + 1) / 10 = 0, 7 |
| 4 |
1 |
(7 * 2 + 1) / 10 = 1, 5 |
| 5 |
0 |
(5 * 2 + 0) / 10 = 1, 0 |
故商 $(11110)_2/10=(00011)_2=(11)_2$，余数为 $0$
将 $(11)_2$ 用作下一次循环的运算数
| 序号 |
当前位 |
运算 |
| 0 |
null |
null |
| 1 |
1 |
(0 * 2 + 1) / 10 = 0, 0 |
| 2 |
1 |
(1 * 2 + 1) / 10 = 0, 3 |
故商 $(11)_2/10=(00)_2=0$，余数为 $3$
循环结束，得到余数序列 $03$，逆序后得到进制转换后的数 $30$
代码实现
这里给出 C++ 的算法实现，使用了大量内置的 STL，如不能使用 STL 库可自行实现相关类型。
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
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include "string"
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
/**
* Mapping a n-base number to a int number
* @param c the n-base number
* return the int number
*/
int GetValue(char c) {
if (c >= '0' && c <= '9') {
return c - '0';
}
if (c >= 'a' && c <= 'z') {
return c - 'a' + 10;
}
if (c >= 'A' && c <= 'A') {
return c - 'A' + 36;
}
return -1;
}
/**
* Convert a big num between different base.
* @param a the string of big num
* @param src_base the base of origin number,
* @param to_base
* @return the sring of big num in src_base
*/
string BaseConvert(string a, int src_base, int to_base = 10) {
if (src_base < 2 || src_base > 62 || to_base < 2 || to_base > 62) {
return reinterpret_cast<const char *>(1);
}
char num_alpha[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int temp = 0;
vector<int> number, quotient, result;
string s;
// 将字母映射为数字
for (char &c : a) {
number.push_back(GetValue(c));
}
auto iter = number.begin();
while (!number.empty()) {
// 得到余数和商
while (iter != number.end()) {
temp *= src_base;
temp += *iter++;
quotient.push_back(temp / to_base);
temp %= to_base;
}
// 得到余数，存入result
result.push_back(temp);
// 清空商的前置0
auto i = quotient.begin();
while (*i == 0 && i != quotient.end()) { i++; }
if (i != quotient.begin()) {
quotient.erase(quotient.begin(), i);
}
// 将商作为下一次的运算数，重置商数组和temp
number = quotient;
quotient.clear();
iter = number.begin();
temp = 0;
}
// 逆序余数位
reverse(result.begin(), result.end());
// 将数字映射为字母
for (int &i:result) {
s += num_alpha[i];
}
return s;
}
int main() {
cout << BaseConvert("11110", 2, 10) << endl;
cout << BaseConvert("30", 10, 2) << endl;
return 0;
}
|
