最近同事参加公司的黑客竞赛，有一道题目与钱币组合问题比较像，记得SICP里面有所描述，正好不是很忙，就试着实现该算法，用Scheme语言开发。
问题描述
假设我们已经有足够多的1分，2分，5分钱币，任意给定金额比如1元，问有多少种组合方式？ 换言之，$$1x+2y+5z = 100$$ 求x,y,z的解有多少个
思路
组合方式的总和应为：
-
任意扣去一种钱币比如1分，1元采用2分，5分两种钱币的组合数，再加上：
-
总额为（1元-1分），采用1分，2分，5分三种钱币的组合数；
很明显这可以很容易用递归实现
稍作一点解释：
a. 上面两步的意思是：不带1分的组合数 + 带1分的组合数 = 全部的组合数； 这是显而易见的
b. 上述第2步，（1元-1分）的意思是：这样可以保证任意一种组合方式再加1分都等于1元，保证至少有1个1分的钱币
(letrec
[
(A (lambda (n d) (if (= 0 (mod n d)) 1 0)))
(B (lambda (n d)
(cond
[(not (pair? d)) 0]
[(null? d) 0]
[(= 0 n) 1]
[(> 0 n) 0]
[(= 1 (length d)) (A n (car d))]
[else
( + (B n (cdr d)) (B (- n (car d)) d))
]
)
)
)
]
[B 100 '(1 2 5)]
)
