Question

4.5.整数转换为任意进制字符串

假设你想将一个整数转换为一个二进制和十六进制字符串。例如，将整数 10 转换为十进制字符串表示为 10，或将其字符串表示为二进制 1010。虽然有很多算法来解决这个问题，包括在栈部分讨论的算法，但递归的解决方法非常优雅。

让我们看一个十进制数 769 的具体示例。假设我们有一个对应于前 10 位数的字符序列，例如 convString =“0123456789”。 通过在序列中查找，很容易将小于 10 的数字转换为其等效的字符串。例如，如果数字为 9 ，则字符串为 convString[9] 或 “9”。如果我们将数字 769 分成三个单个位数字，7，6 和 9，那么将其转换为字符串很简单。数字小于 10 听起来像一个好的基本情况。

知道我们的基本情况是什么意味着整个算法将分成三个部分：

1. 将原始数字减少为一系列单个位数字。
2. 使用查找将单个位数字数字转换为字符串。
3. 将单个位字符串连接在一起以形成最终结果。

下一步是找到改变其状态的方法并向基本情况靠近。由于我们示例为整数，所以考虑什么数学运算可以减少一个数字。最可能的候选是除法和减法。虽然减法可能可以实现，但我们不清楚应该减去多少。使用余数的整数除法为我们提供了一个明确的方向。让我们看看如果我们将一个数字除以我们试图转换的基数，会发生什么。

使用整数除法将 769 除以 10 ，我们得到 76，余数为 9。这给了我们两个好的结果。首先，余数是小于我们的基数的数字，可以通过查找立即转换为字符串。第二，我们得到的商小于原始数字，并让我们靠近具有小于基数的单个数字的基本情况。现在我们的工作是将 76 转换为其字符串表示。再次，我们使用商和余数分别获得 7 和 6 的结果。最后，我们将问题减少到转换 7，我们可以很容易地做到，因为它满足 n < base 的基本条件，其中 base = 10。我们刚刚执行的一系列操作如 Figure 3 所示。请注意，余数位于图右侧框中。

Figure 3

ActiveCode 1 展示了实现上述算法的 Python 代码， 以 2 到 16 之间的任何基数为参数。

def toStr(n,base):
   convertString = "0123456789ABCDEF"
   if n < base:
      return convertString[n]
   else:
      return toStr(n//base,base) + convertString[n%base]

print(toStr(1453,16))

请注意，在第 3 行中，我们检查基本情况，其中 n 小于我们要转换的基数。 当我们检测到基本情况时，我们停止递归，并简单地从 convertString 序列返回字符串。 在第 6 行中，我们满足第二和第三定律 - 递归调用和减少除法问题大小。

让我们再次跟踪算法; 这次我们将数字 10 转换为其基数为 2 的字符串（“1010”）。

Figure 4

Figure 4 显示我们得到的结果，但看起来数字是错误的顺序。该算法是正确的，因为我们首先在第 6 行进行递归调用，然后我们添加余数的字符串形式。 如果我们反向返回 convertString 查找并返回 toStr 调用，则生成的字符串将是反向的！通过延后连接操作直到递归调用返回，我们可以得到正确顺序的结果。这应该能使你想起你在上一章中讨论的栈。