前段时间用类似于散弹式编程的方式,各种猜测-运行验证-修正结果,最终成功转换了一个看起来比较有难度的递归函数.但总觉得很蛋疼,原因如下:
1.虽然正确,但是逻辑搞得比较复杂.现在去看,一头雾水,不知道当时是怎么想的,也没有任何欲望去理解.
2.没有充分利用本地变量,而是保守地把当前栈的数据一股脑绑定到Stack对象上.
3.我需要用一个Class来保存栈吗?是不是太重了?为什么不考虑用一个简单的tuple来实现呢?
def recur(n):
if n==1:
return 1,0
return min([(2*recur(n-i)[0]+2**i-1,i) for i in range(n-1,0,-1)],key=lambda x:x[0]) def readable_recur(n):
if n==1:
return 1,0
possible=[]
for choice in range(n-1,0,-1):
res = readable_recur(n-choice)
value = 2*res[0] + 2**choice-1
possible.append((value,choice))
res = min(possible,key=lambda x:x[0])
return res def while_stacks(n):
stacks = [(0,n,[],None,)]
while stacks:
stg,n,possible,choice=stacks.pop()
if stg==0:
if n==1:
res = 1,0
else:
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])
return res
这次是彻底理解了recur递归过程中栈的变化过程,因此写出来的while思路也很清晰,绝对不会像上次那样复杂蛋疼让人没有阅读的欲望.对比上次那一大坨,性能也更好了.快了一倍.