4.5.整数转换为任意进制字符串
Last updated
Last updated
假设你想将一个整数转换为一个二进制和十六进制字符串。例如,将整数 10
转换为十进制字符串表示为 10
,或将其字符串表示为二进制 1010
。虽然有很多算法来解决这个问题,包括在栈部分讨论的算法,但递归的解决方法非常优雅。
让我们看一个十进制数 769
的具体示例。假设我们有一个对应于前 10
位数的字符序列,例如 convString =“0123456789”
。 通过在序列中查找,很容易将小于 10
的数字转换为其等效的字符串。例如,如果数字为 9
,则字符串为 convString[9] 或 “9”。如果我们将数字 769
分成三个单个位数字,7
,6
和 9
,那么将其转换为字符串很简单。数字小于 10 听起来像一个好的基本情况。
知道我们的基本情况是什么意味着整个算法将分成三个部分:
将原始数字减少为一系列单个位数字。
使用查找将单个位数字数字转换为字符串。
将单个位字符串连接在一起以形成最终结果。
下一步是找到改变其状态的方法并向基本情况靠近。由于我们示例为整数,所以考虑什么数学运算可以减少一个数字。最可能的候选是除法和减法。虽然减法可能可以实现,但我们不清楚应该减去多少。使用余数的整数除法为我们提供了一个明确的方向。让我们看看如果我们将一个数字除以我们试图转换的基数,会发生什么。
使用整数除法将 769
除以 10
,我们得到 76
,余数为 9
。这给了我们两个好的结果。首先,余数是小于我们的基数的数字,可以通过查找立即转换为字符串。第二,我们得到的商小于原始数字,并让我们靠近具有小于基数的单个数字的基本情况。现在我们的工作是将 76
转换为其字符串表示。再次,我们使用商和余数分别获得 7
和 6
的结果。最后,我们将问题减少到转换 7
,我们可以很容易地做到,因为它满足 n < base
的基本条件,其中 base = 10
。我们刚刚执行的一系列操作如 Figure 3 所示。请注意,余数位于图右侧框中。
Figure 3
ActiveCode 1 展示了实现上述算法的 Python 代码, 以 2 到 16 之间的任何基数为参数。
请注意,在第 3 行中,我们检查基本情况,其中 n 小于我们要转换的基数。 当我们检测到基本情况时,我们停止递归,并简单地从 convertString 序列返回字符串。 在第 6 行中,我们满足第二和第三定律 - 递归调用和减少除法问题大小。
让我们再次跟踪算法; 这次我们将数字 10 转换为其基数为 2 的字符串(“1010”)。
Figure 4 显示我们得到的结果,但看起来数字是错误的顺序。该算法是正确的,因为我们首先在第 6 行进行递归调用,然后我们添加余数的字符串形式。 如果我们反向返回 convertString 查找并返回 toStr 调用,则生成的字符串将是反向的!通过延后连接操作直到递归调用返回,我们可以得到正确顺序的结果。这应该能使你想起你在上一章中讨论的栈。
Figure 4