我的问题来自河内的一个变体，它有四座塔楼。
我知道这篇文章说在c ++中，您可以将任何递归函数转换为循环，但我只熟悉Python。我试图阅读十条规则，但是关键字struct和stack对python意味着什么？
因此，任何与上面C++类似的 python 文章或讨论也非常感谢。谢谢。
原始递归函数是fmove(tmove持有另一个递归函数)，接收一个整数，返回一个元组。它很优雅，但没用(试着tmove(100)，小心你的记忆)。
我想将其转换为纯收益循环版本，这样即使 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,)
在这个问题中user2357112的帮助下，我知道如何转换递归函数，如tmove- 返回递归(...+ 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
经过几天的学习，借助 c++ 文章，我终于自己得到了纯循环版本。我认为@Javier是对的——不可能屈服。
def best(n):
"""
n -> best_cut_number
four-towers Hanoi best cut number for n disks.
"""
stacks = [(0,n,[],None,)] #(stg,n,possible,choice)
cache={1:(1,0)}
while stacks:
stg,n,possible,choice=stacks.pop()
if n in cache:
res = cache[n]
elif stg==0:
stacks.append((1,n,possible,n-1))
stacks.append((0,1,[],None))
else:
value = 2*res[0] + 2**choice-1
possible.append((value,choice))
if choice > 1:
stacks.append((1,n,possible,choice-1))
stacks.append((0,n-choice+1,[],None))
else:
res = min(possible,key=lambda x:x[0])
cache[n] = res
best_cut_number = res[1]
return best_cut_number