我的问题来自河内的变体,它有四座塔。
我知道this article它说在 C++ 中你可以将任何递归函数转换为循环,但我只熟悉 Python。我试图阅读这十条规则,但是关键字 struct
和 stack
对 python 意味着什么?
因此,任何与上述 C++ 类似的 python 文章或讨论也非常受欢迎。谢谢。
原始递归函数是fmove
(包含另一个递归函数tmove
),接收一个整数,返回一个元组对。它很优雅但没用(尝试 tmove(100)
并注意你的内存)。
我想将它转换为纯 yield 循环版本,这样即使 n 变大到 100 或 1000,我仍然可以知道元组的前 10 对或 100 对是什么。
def memory(function):
"""
This is a decorator to help raw recursion
functions to avoid repetitive calculation.
"""
cache = {}
def memofunc(*nkw,**kw):
key=str(nkw)+str(kw)
if key not in cache:
cache[key] = function(*nkw,**kw)
return cache[key]
return memofunc
@memory
def tmove(n, a=0, b=1, c=2):
"int n -> a tuple of pairs"
if n==1:
return ((a,c),)
return tmove(n-1,a,c,b)+\
((a,c),)+\
tmove(n-1,b,a,c)
@memory
def fmove(n,a=0,b=1,c=2,d=3):
"int n -> a tuple of pairs"
if n==1:
return ((a,d),)
return min(
(
fmove(n-i,a,d,b,c) +
tmove(i,a,b,d) +
fmove(n-i,c,b,a,d)
for i in range(1,n)
),
key=len,)
在 this question 用户 2357112 的帮助下,我知道如何转换像 tmove
这样的递归函数——return recur(...)+ CONS 或另一个调用 +recur(...),但是当情况变得更复杂时,比如 fmove
,我不知道如何设计结构,-- i
与 n
相关,在不同的堆栈中是不同的,你终于有了使用 min
获取最小大小的元组作为当前堆栈的正确输出。
这是我的尝试(核心算法best(n)
仍然是递归函数):
@memory
def _best(n):
if n==1:
return 1,1
return min(
(
(i, 2*(_best(n-i)[1])+2**i-1)
for i in range(1,n)
),
key=lambda x:x[1],
)
def best(n):
return _best(n)[0]
def xtmove(n,a=0,b=1,c=2):
stack = [(True,n,a,b,c)]
while stack:
tag,n,a,b,c = stack.pop()
if n==1:
yield a,c
elif tag:
stack.append((False,n,a,b,c))
stack.append((True,n-1,a,c,b))
else:
yield a,c
stack.append((True,n-1,b,a,c))
def xfmove(n,a=0,b=1,c=2,d=3):
stack = [(True,n,a,b,c,d)]
while stack:
is_four,n,a,b,c,d = stack.pop()
if n==1 and is_four:
yield a,d
elif is_four:
# here I use a none-tail-recursion function 'best'
# to get the best i, so the core is still not explicit stack.
i = best(n)
stack.append((True,n-i,c,b,a,d))
stack.append((False,i,a,b,d,None))
stack.append((True,n-i,a,d,b,c))
else:
for t in xtmove(n,a,b,c):
yield t
这是测试代码。确保您可以通过它。
if __name__=='__main__':
MAX_TEST_NUM = 20
is_passed = all((
fmove(test_num) == tuple(xfmove(test_num))
for test_num in range(1,MAX_TEST_NUM)
))
assert is_passed, "Doesn't pass the test."
print("Pass the test!")
最佳答案
fmove
对其递归调用和对 tmove
的调用的所有值执行 min
,因此在这个案例。您需要完成 100% 的调用才能获得 min
的结果。
关于堆栈方法,它正在创建一个带有 2 个操作码(True 和 False)的最小解释器。 :)
看看 tmove 如何可以流式传输结果,而不会重复使用没有生成器的语言所必需的陈旧技术。
from itertools import chain
def xtmove(n, a=0, b=1, c=2):
"int n -> a tuple of pairs"
if n==1:
yield (a,c)
else:
for i in chain(xtmove(n-1,a,c,b), [(a,c)], xtmove(n-1,b,a,c)):
yield i
关于Python 3.3 如何将此递归函数转换为纯 yield 循环版本?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21978463/