问题来自SICP.
该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] = [...]