Python中的回溯

Question

我刚开始学习Python并试图写下回溯算法，但似乎我做错了什么。 由于我对这门语言不太熟悉，我一直在网上查它，但不太懂它。在这里我的代码是：

n = 3
x = [0] * 3
k = 0
def init ():
    x[k] = 0
def succesor():
    if x[k] < n:
        x[k]+=1
        return 1
    return 0
def valid ():
    i = 1
    for i in range (0,k-1):
        if x[i] == x[k]:
            return 0
    return 1
def solutie ():
    return k == n
def afis():
    print(x)
def back ():
    k = 1
    avemsuccesor = 1
    init()
    while k > 0:
        while avemsuccesor and not valid():
            avemsuccesor = succesor()
        if avemsuccesor:
            if solutie:
                afis()
            else:
                k+=1
                init()
        else:
            k-=1
def main ():
    back()
main ()

当我运行它时，我只得到一个向量的0。 你能帮帮我吗？在

Answer 1

问题是k被定义了两次，一次是0，一次是1。在valid中，它选择全局k=0，但是不管怎样，即使k-1最初也是零，所以valid（）在第一次迭代时将返回1。我不明白这个程序的意图，但这就是它永远不能运行succeer（）的原因，它实际上是从零修改向量的元素。在

Answer 2

一个关键问题是：

if solutie:

正在测试函数的真实性，它将始终是True：

^{pr2}$

而不是它返回的值的真实性；您应该：

if solutie():
        # ^ note parentheses

而且，您的函数都没有参数，因此您完全依赖变量范围进行访问。这是不明智的，并且使代码很难调试-您不能单独测试任何函数。作为一个简单的例子，请比较：

def solutie():
    return k == n

与

def solutie(k, n):
    return k == n

对于前者，测试非常困难-k和{}是什么？他们从哪里来的？对于后者，这是一个简单的问题

assert solutie(1, 1)
assert not solutie(1, 2)

您的主要问题源于此：因为k是不可变的，所以除了back之外，在每个函数中总是使用相同的值。尽管您在back中分配了k += 1，但其他函数（例如valid）仍在从外部范围使用k == 0。如果您将每个函数更改为使用显式参数和返回值，例如：

 def successor(x, k, n):
     ...
     return True # use booleans rather than 0 or 1

 ...
     avemsuccesor = succesor(x, k, n) 

您将很快发现k超出范围，导致IndexError。我不会在这里重写所有的东西——我将留下重构代码来显式地传递值，并解决随后作为练习出现的错误。在