原文链接 http://woodrat.xyz/2014/10/05/%e6%8d%a2%e9%9b%b6%e9%92%b1%e9%97%ae%e9%a2%98/
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。
刚刚看了欧拉计划31题.一下就想起了sicp上的练习2.19了,由于时间隔的太久,一下子想不起当时写的解法了=.=
只记得是一个简单的递归....感觉智商一直在下降啊
思路如下:
假设有N种硬币,那么换零钱方式的数目,等于完全不使用第一种硬币的方式的数目,加上使用第一种硬币的方式的数目.
scheme的一种解法如下
(define (cc amount coin-values) (define (no-more? a) (null? a)) (define (except-first-demonination list) (cdr list)) (define (first-demonination list) (car list)) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-demonination coin-values)) (cc (- amount (first-demonination coin-values)) coin-values)))))
对应可以写出C语言的递归解法
#include static int pence[] = {1, 2, 5, 10, 20, 50, 100, 200}; static int total_amount = 200; int findallpos(int amount, int i) { if(amount == 0) return 1; else if(i>7 || amount < 0) return 0; return(findallpos(amount - pence[i], i) + findallpos(amount, i+1)); }
int main() { printf("%d\n",findallpos(total_amount, 0)); return 0; }