Collatz猜想的Python递归函数

3mpgtkmj  于 2023-01-04  发布在  Python
关注(0)|答案(4)|浏览(138)

我写了下面的递归程序来显示一个数在Collatz猜想中经过的步数:

def cycle_length(n):
    count = 0
    if n == 1:
        return count
    if n%2 == 0:
        count += cycle_length(int(n/2)) +1
    elif n%2 != 0:
        count += cycle_length(int(3*n+1)) + 1
        print("The count is: ",count)
    return count 

print(cycle_length(22))

然而,计数是15时,它应该是16。然而,当我改变初始计数为1或说:

return count + 1

它使计数加倍到31。我不知道是什么引起的。
谢谢你的帮助。

toe95027

toe950271#

n为1时,需要将count递增1才能返回。

def cycle_length(n):
    count = 0
    if n == 1:
        return count + 1 # or simply return 1
    ...

但是我认为如果您不选择计算第零步,那么您的代码在语法上是正确的。
参见http://oeis.org/A070165

yvt65v4c

yvt65v4c2#

当你设置count=1时,你不应该在后面的if,else if语句中设置count+=。而且,在我看来,你之前的答案已经是正确的了。但是,如果你想在上面加1(即当1出现时计算步数),只需做以下操作:

def cycle_length(n):
    count = 1
    if n == 1:
        return count
    if n%2 == 0:
        count = (cycle_length(int(n/2)) +1)
    elif n%2 != 0:
        count = (cycle_length(int(3*n+1)) + 1)
    return count
bn31dyow

bn31dyow3#

Collatz序列总是从给定的数字开始,因此基本情况应该是返回1
也就是说,你也可以使用迭代来计算它,因为python不太喜欢递归,例如,你的代码不能计算9780657631或75128138247而不得到递归错误
这是迭代版本

def collatz_length(n):
    if n<1:
        raise ValueError
    count = 1
    while n != 1:
        if n%2 == 0:
            n = n//2
        else:
            n = 3*n+1
        count += 1
    return count
kzipqqlq

kzipqqlq4#

试试这个

def cc(n):
    print(n)
    if(n%2==0):
        return cc(n/2)
    elif(n==1):
        return 1
    else:
        return cc(n*3+1)
print(cc(7))

相关问题