换零钱方式的统计

换零钱方式的统计 问题:给 半美元、四分之一美元、10美分、5美分、1美分的硬币，将任意数量的现金换成零钱，共有多少总不同方式, 算法 1 递归过程 思路: 设，总数为a，硬币总数为n，那么总数目等于 将a换成除第一种硬币外，所有其他硬币的不同方式的数目，加上 将a-d换成不同硬币的总数目，其中d为第一种硬币的币值 注意: 如果a=0，应作为有1种换零钱方式 如果a<0，应作为有0种换零钱方式 如果n=0，应作为有0种换零钱方式 (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50))) 算法 2 算法分析: 1. 该算法产生出一个属性的递归计算过程，可以看到对这一问题要出迭代算法就没那 么明显了。 2. 分析算法的写法，可以看出在初始化硬币总类和币值是不那么自然，对比种的把握是通 过一个数值形式的kinds-of-coins来区分，比较生硬，要变出程序来也就要了解示法， 相比较而言如果是面向对象语言，那么可以很自然用类来定义。 迭代过程:初步分析，所需空间并非常量，应为一个栈空间，且大小不超过a*n. 利用表来提供可用于兑换的硬币，算法: (define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5)) (define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values))))) (define (no-more? items) (null? items)) (define (except-first-denomination items) (cdr items)) (define (first-denomination items) (car items)) (cc 100 us-coins) (cc 100 uk-coins) 292 104561