[已解决]怎么对汉诺塔问题的移动次数进行计数？

环境过程发明家

如题，想在小甲鱼老师写的汉诺塔递归程序上添加统计移动次数的功能（知道次数可以直接打印最终结果2^n-1,但是还是想通过逐次计数来得出结果）
现在写的程序是这样的
time=0
def hanoi(n,start,media,target):
    global time
    if n == 1:
        print(start,"--->",target)
        time+=1
    else:
        hanoi(n-1,start,target,media)
        print(start,"--->",target)
        time+=1
        hanoi(n-1,media,start,target)
    return(time)


多次运行时，第一次能得出正确结果（7），第二次以后打印的次数则是在第一次基础上进行的累加（14）（如图）。请问这个程序要怎样修改呢？

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-3-24 11:12:13

def hanoi(n,start,media,target):
    time=0
    if n == 1:
        print(start,"--->",target)
        time+=1
    else:
        time+=hanoi(n-1,start,target,media)
        print(start,"--->",target)
        time+=1
        time+=hanoi(n-1,media,start,target)
    return(time)
    
print(hanoi(3,'a','b','c'))
print(hanoi(3,'a','b','c'))

跳转到最佳答案楼层

TCY

在函数第二行加一句：

time = 0

qiuyouzhi

TCY 发表于 2020-3-24 10:20
在函数第二行加一句：

你那样不行，每次递归都会被重置

sunrise085

def hanoi(n,start,media,target):
    time=0
    if n == 1:
        print(start,"--->",target)
        time+=1
    else:
        time+=hanoi(n-1,start,target,media)
        print(start,"--->",target)
        time+=1
        time+=hanoi(n-1,media,start,target)
    return(time)
    
print(hanoi(3,'a','b','c'))
print(hanoi(3,'a','b','c'))

coolsummer2080

不能使用全局变量。

zltzlt

可以使用闭包解决：

def func(n, s, m, t):
    time = 0

    def hanoi(n, start, media, target):
        nonlocal time
        if n == 1:
            print(start, "--->", target)
            time += 1
        else:
            hanoi(n - 1, start, target, media)
            print(start, "--->", target)
            time += 1
            hanoi(n - 1, media, start, target)
        return time

    return hanoi(n, s, m, t)


print(func(3, "a", "b", "c"))
print(func(3, "a", "b", "c"))

环境过程发明家

sunrise085 发表于 2020-3-24 11:12

time+=hanoi(n-1,start,target,media)
这句没看懂  能解释一下嘛 谢谢

sunrise085

环境过程发明家 发表于 2020-3-24 15:49
time+=hanoi(n-1,start,target,media)
这句没看懂  能解释一下嘛 谢谢

time+=hanoi(n-1,start,target,media)
就是
time = time + hanoi(n-1,start,target,media)
函数的返回值是移动的次数，这句话就是把递归调用时所计数的次数返回来与本次调用的计数值相加。
也就是把多层递归中移动的次数相加。
不太理解的话，可以这样写，或许更好理解。

def hanoi(n,start,media,target):
    time=0
    if n == 1:
        print(start,"--->",target)
        time+=1
    else:
        t1=hanoi(n-1,start,target,media)
        time =time+t1
        print(start,"--->",target)
        time+=1
        t2=hanoi(n-1,media,start,target)
        time=time+t2
    return(time)
    
print(hanoi(3,'a','b','c'))
print(hanoi(3,'a','b','c'))