河内塔-一组动作

Question

def hanoi(n,src,dsc,aux):
    if n == 1:
        print_move(src,dsc)
    else:
        hanoi(n-1,src,aux,dsc)
        print_move(src,dsc)
        hanoi(n-1,aux,dsc,src)

def print_move(src,dsc):
    print("Move the top disk from",src,"to",dsc)

我希望更改上面的汉诺塔代码，以输出一个移动元组，当按顺序执行时，将通过辅助磁极将所有磁盘从源极移动到目标磁极。磁盘移动被定义为一对两个数字:源极和目的极。例如，(1, 3)表示磁盘从第一极移动到第三极。因此，hanoi(2,1,3,2)将输出((1,2),(1,3),(2,3))

我的方法是创建一个名为tup的全局变量，这是一个空元组。然后，每当创建新的元组移动时，它都会被添加到tup中。我的问题是，我不知道何时应该返回tup的值，也不知道在hanoi函数中可以将return行放在哪里。

Answer 1

在递归函数中实现这一点的最佳方法通常如下所示：

def hanoi(..., out=None):
    if out is None:
        out = [] # list to store output
    ...
    print_move(src, dsc)
    out.append((src, dsc)) # add result to output
    ...
    hanoi(..., out) # call recursively and ignore return
    ...
    return out # return output

(请注意，使用None可以避免可变默认参数的问题。)

当呼叫时：

results = hanoi(...)

这样，所有级别的递归调用都可以共享和添加一个列表out。每次调用都会忽略更深层调用的返回值，因为它们无论如何都可以访问相同的列表，但顶级调用者会从所有级别获取输出。

对于存储来说，列表比元组更好，因为列表是可变的，但每次移动使用两个元组似乎是合理的：

results == [(1, 2), (1, 3), (2, 3)]