跳转至

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

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

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

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

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

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

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

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

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

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”)。

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

Figure 4

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