对付冗余计算…的那个途径
该Sample描述了一个换硬币的问题，卡卡，就是偶们是小朋友的是哈哈，父亲大人/母亲大人可能给你一张大..大的钞票，出去打酱油..:D，花不完的，老板会找你钱。找多少钱是个思想斗争，于是就有了这个问题。
给予一定的硬币种类kinds-of-coins和一定的金额amount，使用这些硬币有多少种方式能组成这个金额呢？
很简单哈，所以就书上直接就是源码鸟（这里）。
可惜哈，这个代码实现的是一个树状递归，而树状递归的效率是非常的龌龊，不信你可以试试画一下amount=11, kinds-of-coins=5时的递归计算过程，这个树的很多枝枝丫丫都是一样de，骗取社会主义劳动成功，死人领着活人工资。
所以在脚注34里就提到一种对付这些枝枝丫丫的政策，所谓“记忆技术”（memoization）就是了。
脚注里面说得很呆，其实很简单，把已经算得的结果缓存起来，然后遇到同样的计算任务的时候拿出来用就好。练习3.27就是这么搞的，可惜scheme里面木有构造Cache的现成数据结构，要我实现dic,hash table,什么的我那么lazy的所以不愿意的。不过我的实现也不大优雅，memorize和被memorize的函数杂糅到一起了，python高手告诉我，有木有办法分开？
import time
def change_coins(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
def cc((amount, kinds_of_coins)):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc((amount, kinds_of_coins - 1)) \
+ cc((amount - first_denomination[kinds_of_coins], kinds_of_coins))
return cc((money, 5))
def change_coins_memoization(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
cache = {}
cc_memo = lambda x :memoize(cc) (x)
def memoize(fun):
def proc(k):
if cache.has_key(k):
return cache[k]
else:
x = fun(k)
cache[k] = x
return x
return proc
def cc((amount, kinds_of_coins)):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc_memo((amount, kinds_of_coins - 1)) + \
cc_memo((amount - first_denomination[kinds_of_coins], kinds_of_coins))
return cc_memo((money, 5))
if __name__ == "__main__":
money = int(raw_input())
start = time.clock()
print "change_coins return %s cost %fs" % (change_coins(money), (time.clock()-start))
start = time.clock()
print "change_coins_memoization return %s cost %fs" % (change_coins_memoization (money), (time.clock()-start))
python的那个栈的深度有限(讨厌得很，而且还不优化尾递归)，输入300就差不多鸟，来看看memoization的小宇宙怎样爆发的：
change_coins return 9590 cost 1.100000s change_coins_memoization return 9590 cost 0.000000s
做剪枝的时候也用到的。
