2

我正在编写一个函数，它接受一个参数'n'，它将使用递归公式将十进制数转换为二进制数。

这就是我所拥有的非递归函数，但我需要弄清楚如何递归地编写它。

def dec2bin(n):
    bStr = ''
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        return '0'
    else:
        bStr += str(n%2)
    return bStr
4

5 回答 5

6

想想你的基本情况。将答案直接写入程序对哪些输入有意义？0? 1？可能仅此而已；你不希望一条巨大的elif连锁店上升到“好吧，如果是 314，我们可以返回'100111010'”。想想你需要多少个数字来硬编码答案，作为递归的一种基础，以及你可以并且应该让算法处理哪些数字。

想想你的递归调用。如果您想生成 的二进制表示n，那么什么调用dec2bin会为您提供大部分答案，那么您可以稍微修改一下结果并返回它？好吧，如果n大于1，则 的二进制表示n是 的二进制表示，n//2末尾有另一个数字，就像 的十进制表示n是n//10末尾有另一个数字的十进制表示一样。

于 2013-07-21T01:33:13.097 回答
6

你的代码几乎没问题。您实际上不必维护bStr. 假设您知道n//2然后二进制表示的二进制表示n是的二进制表示n//2并且0如果可以被或n整除。21

喜欢n= 3。n//2= 1。dec2bin(n//2) = '01'so dec2bin(n)= '01'+'1'[因为3不能被 整除2] ='011'

你的代码应该是这样的。

def dec2bin(n):
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        return '0'
    else:
        return dec2bin(n//2) + str(n%2)

就这样。

于 2013-07-21T06:34:57.710 回答
1

这是@Stickysli 对@rnbguy 解决方案的“改进”的后续行动。正在解决的问题是不必要的前导 0，但以不为零本身产生空结果的方式消除它。提议的“改进”非常复杂（是原始代码行数的两倍多）并且依赖于写入全局变量！

我相信我们可以用比原来更少的代码行来解决问题，方法是使用测试来查看我们是否在数字 1 上递归，因为这是问题的根源：

def dec2bin(n):
    if n < 0:
        raise ValueError("Must be a positive integer")

    digit = str(n % 2)

    return dec2bin(n // 2) + digit if n > 1 else digit

后：

>>> dec2bin(22)
'10110'
>>> dec2bin(0)
'0'
>>>
于 2019-03-31T05:38:45.867 回答
1

为了改进rnbguy的答案，我发现当您的输入是除 之外的任何数字时0，它实际上确实返回了二进制表示，'0'最后带有一个附加值。

要删除它，我想出的唯一解决方案是添加一个全局变量，该变量记住模数的先前值n%2：

prev = 0
def dec2bin(n):
    global prev
    if n < 0:
        return 'Must be a positive integer'
    elif n == 0:
        if prev == 0:
            return '0'
        else:
            prev = 0
            return ''
    else:
        m = n%2
        prev = m
        return dec2bin(n//2) + str(m)

这背后的原因是当你尝试divmod(0, 2)输出时(0, 0)，所以我们知道输出必须是简单的'0'。但是，如果我们有一个大于 0 的数字，递归函数将始终结束除法1//2，1%2并且输出与 相同divmod(1, 2) == (0, 1)。

为了在我们的输出结束时规避另一个'0'，我们会将1of保存1%2在全局变量中，并在第二种情况下prev检查它，因为我们目前有.prev != 0n = 0

之前：

>>> print dec2bin(22)
010110
>>> print dec2bin(0)
0

之后：

>>> print dec2bin(22)
10110
>>> print dec2bin(0)
0

请注意，我们必须在prev = 0旁边添加return ''，否则print dec2bin(0)自上次执行的代码将设置prev为1.

于 2019-03-30T19:03:35.990 回答
0

修改所有答案。

解决方案 1

def dec2bin(num):
    if num == 0:
        return "" 
    else:
        return dec2bin(num//2) + str(num%2)

调用函数为：

dec2bin(233)

解决方案 2

def dec2bin(num, result):
    if num == 0:
        return result 
    
    result = str(num % 2) + result
    return dec2bin(num//2, result)

调用函数为：

dec2bin(233, "")
于 2021-12-26T16:38:29.663 回答