「大数问题」大数任意进制转换

发表于： 更新于： 分类于：
字数：1330 阅读：≈ 3分钟 浏览： 评论：

写算法题的时候经常会碰到一些大数相关的问题，比如大数乘法、大数加法等等，乘法和加法的原理基本上都比较符合正常的思维模式，因为加法和乘法的原理相对清晰，模拟数学计算步骤可以方便地分离，并转换为代码。

相对于常见的加法和乘法，进制转换出现的频率低一些，但同样是一个十分值得探讨的问题，并且难度较之加法和乘法更高。

问题抽象

  • 输入为 ($M$, $m$, $n$):

    • $M$: $m$ 进制整数 $M$，用字符串类型 string 储存
    • $m$: 大数基数 $m$
    • $n$: 大数目的基数 $n$

  • 输出为 N：

    • $N$: $n$ 进制整数 $N$，用字符串类型 string 储存

数学原理

$m$ 进制转换成 $n$ 进制，通常采用的是「模 $n$ 取余法」，也称「辗转相除法」，一般数进制转换的方法：

  1. 输入 $m$ 进制数 $M$ 作为除数，对目标进制基数 $n$ 求整数商得到商 $Q^1$ ，对基数 $n$ 取余得到余数 $R^1$，

  2. 若商 $Q^1$ 为 $0$，循环终止，否则，用商 $Q^1$ 作为除数，继续对基数 $n$ 求整数商得到商 $Q^2$，取余得到余数 $R^2$，

  3. 循环第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

可以想象，大数转换步骤同样如此。

问题只在于大数的整数除和取余比一般数字更复杂一些，这里将算法解释如下：

  1. 设余数 $R=0$

  2. 由低位至高位，从大数中取数 $M^1$，用余数 $R$ 乘以进制基数 $m$ 后再加上数 $M^1$，得到数 $R \cdot m + M^1$，用该数对目标进制基数 $n$求整数商得到商 $Q^1$，对基数 $n$ 取余得到新的余数 $R$

  3. 循环第2步，直至取完大数所有位，得到商 $Q^t$ 和余数 $R$

    则商序列 $Q^tQ^{t-1}\cdots Q^1$ 为整数商，$R$ 为余数。

eg. $(11110)_2 \to 30$

序号当前位运算
0nullnull
11(0 * 2 + 1) / 10 = 0, 1
21(1 * 2 + 1) / 10 = 0, 3
31(3 * 2 + 1) / 10 = 0, 7
41(7 * 2 + 1) / 10 = 1, 5
50(5 * 2 + 0) / 10 = 1, 0

故商 $(11110)_2/10=(00011)_2=(11)_2$，余数为 $0$

将 $(11)_2$ 用作下一次循环的运算数

序号当前位运算
0nullnull
11(0 * 2 + 1) / 10 = 0, 0
21(1 * 2 + 1) / 10 = 0, 3

故商 $(11)_2/10=(00)_2=0$，余数为 $3$

循环结束，得到余数序列 $03$，逆序后得到进制转换后的数 $30$

代码实现

这里给出 C++ 的算法实现，使用了大量内置的 STL，如不能使用 STL 库可自行实现相关类型。

 1#include "string"
 2#include "iostream"
 3#include "vector"
 4#include "algorithm"
 5
 6using namespace std;
 7
 8/**
 9 * Mapping a n-base number to a int number
10 * @param c the n-base number
11 * return the int number
12 */
13int GetValue(char c) {
14    if (c >= '0' && c <= '9') {
15        return c - '0';
16    }
17    if (c >= 'a' && c <= 'z') {
18        return c - 'a' + 10;
19    }
20    if (c >= 'A' && c <= 'A') {
21        return c - 'A' + 36;
22    }
23    return -1;
24}
25
26/**
27 * Convert a big num between different base.
28 * @param a the string of big num
29 * @param src_base the base of origin number,
30 * @param to_base
31 * @return the sring of big num in src_base
32 */
33string BaseConvert(string a, int src_base, int to_base = 10) {
34    if (src_base < 2 || src_base > 62 || to_base < 2 || to_base > 62) {
35        return reinterpret_cast<const char *>(1);
36    }
37
38    char num_alpha[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
39    int temp = 0;
40    vector<int> number, quotient, result;
41    string s;
42
43    // 将字母映射为数字
44    for (char &c : a) {
45        number.push_back(GetValue(c));
46    }
47    auto iter = number.begin();
48
49    while (!number.empty()) {
50        // 得到余数和商
51        while (iter != number.end()) {
52            temp *= src_base;
53            temp += *iter++;
54            quotient.push_back(temp / to_base);
55            temp %= to_base;
56        }
57        // 得到余数，存入result
58        result.push_back(temp);
59        
60        // 清空商的前置0
61        auto i = quotient.begin();
62        while (*i == 0 && i != quotient.end()) { i++; }
63        if (i != quotient.begin()) {
64            quotient.erase(quotient.begin(), i);
65        }
66
67        // 将商作为下一次的运算数，重置商数组和temp
68        number = quotient;
69        quotient.clear();
70        iter = number.begin();
71        temp = 0;
72    }
73
74    // 逆序余数位
75    reverse(result.begin(), result.end());
76    // 将数字映射为字母
77    for (int &i:result) {
78        s += num_alpha[i];
79    }
80
81    return s;
82}
83
84int main() {
85    cout << BaseConvert("11110", 2, 10) << endl;
86    cout << BaseConvert("30", 10, 2) << endl;
87
88    return 0;
89}