我编写了一个简短的程序来显示DFA的可能输出。事实上,它给出了预期的结果。但是我一直在尝试重写这个函数,以便它返回结果,而不是使用全局变量--我想不出怎么做。请有人解释一下,如果不使用全局变量,我将如何做到这一点?
result = set()
def gen_strings(max_length, state = "A", str = ""):
global result
if len(str) > max_length:
return
if state == "A":
gen_strings(max_length, "B", str + "0")
gen_strings(max_length, "C", str + "1")
elif state == "B":
gen_strings(max_length, "D", str + "1")
elif state == "C":
gen_strings(max_length, "D", str + "0")
elif state == "D":
result.add(str)
gen_strings(max_length, "A", str + "0")
gen_strings(max_length, "A", str + "1")发布于 2014-09-04 02:42:02
这里有两种选择:自上而下的积累,或自下而上。
如果你做的是自下而上的话,你可以不需要任何变异就能做到。这确实使将递归编写为尾调用变得更加困难(有时是不可能的),但这很好,因为(a) Python无论如何都不会消除尾调用,而且(b)即使这样做了,算法也不会受益,因为它会进行多次调用。所以,我先展示一下:
def gen_strings(max_length, state = "A", str = ""):
if len(str) > max_length:
return set()
if state == "A":
return (gen_strings(max_length, "B", str + "0") |
gen_strings(max_length, "C", str + "1"))
elif state == "B":
return gen_strings(max_length, "D", str + "1")
elif state == "C":
return gen_strings(max_length, "D", str + "0")
elif state == "D":
return ({str} |
gen_strings(max_length, "A", str + "0")
gen_strings(max_length, "A", str + "1"))要做到自顶向下,只需将result传递给state和str,就像向下传递一样:
def gen_strings(max_length, state="A", str="", result=None):
if len(str) > max_length:
return
if state == "A":
gen_strings(max_length, "B", str + "0", result)
gen_strings(max_length, "C", str + "1", result)
# etc.问题是,这不会返回结果,而是将其作为参数--您必须在顶层传递一个空集,如下所示:
result = set()
gen_strings(max_length, result=result)但你总能把它包起来。将gen_strings重命名为gen_strings_r,然后编写如下:
def gen_strings(max_length, state="A", str=""):
result = set()
gen_strings_r(max_length, state, str, result)
return result或者你可以将两者结合起来,向下传递一个值,用于构建一个向上返回的值。这给了你自下而上(避免变异)和自上而下(允许尾叫)的好处,这使得它成为函数式语言中非常常见的成语,尤其是纯函数式语言。但在这种情况下,它并不比普通的自下而上更有优势,而且它需要对代码进行更大的更改,所以我不会费心地编写它。
发布于 2014-09-04 02:50:14
你可以做个了结:
def gen_str(max_length, state = "A", str = ""):
result = set()
def rec_gen_strings(max_length, state = "A", str = ""):
if len(str) > max_length:
return
if state == "A":
rec_gen_strings(max_length, "B", str + "0")
rec_gen_strings(max_length, "C", str + "1")
elif state == "B":
rec_gen_strings(max_length, "D", str + "1")
elif state == "C":
rec_gen_strings(max_length, "D", str + "0")
elif state == "D":
result.add(str)
rec_gen_strings(max_length, "A", str + "0")
rec_gen_strings(max_length, "A", str + "1")
rec_gen_strings(max_length, state, str)
return resulthttps://stackoverflow.com/questions/25656475
复制相似问题