首页 > 代码库 > SICP 习题 (2.19) 解题总结:重写零钱兑换程序
SICP 习题 (2.19) 解题总结:重写零钱兑换程序
SICP 习题2.19 要求我们重新设计1.2.2节的零钱兑换程序,要求我们可以轻易改变程序里用的兑换币种。
我们先看看1.2.2节的零钱兑换程序,代码是这样的:
(define (RMB-Change amount) (format #t "Changing ~S~%" amount) (cond ((= amount 0) 0) ((< amount 0) 0) (else (RMB-Change-Recursive amount 1 ‘() )))) (define (RMB-Change-Recursive amount change-kind change-result) (format #t "( ~S ~S )" amount change-kind) (if (= amount 0) (format #t "Got one: ~S~%" change-result)) (cond ((= amount 0) 1) ((> change-kind amount) 0) ((= change-kind 0) 0) (else (+ (RMB-Change-Recursive amount (RMB-Change-Next-Kind change-kind) change-result) (RMB-Change-Recursive (- amount change-kind) change-kind (cons change-kind change-result))))))
注意,我这里的代码是我自己写的,和书中的样例代码有出入。
不过我们需要留意的是代码的思路,所以不需要留意代码细节。
1.2.2节中的零钱兑换程序的主要思路就是将遍历所有面额,对每一种面额的钱币都对当前需要兑换的总数做两种假设,一是零钱兑换方式包括了当前面额,第二种是零钱兑换方式没包括当前面额。
对第一种方式,就是将当前需要兑换的总数减当前面额,产生新的需要兑换的总数,然后递归处理。
对第二种方式,就是将当前面额的从所有面额中除去,看当前总数对应剩下的面额有多少兑换方式,然后递归处理。
为了方便地使用以上方法计算不同国家的币种,简单的方式就是将不同国家的零钱组合做成一个list,然后计算过程中就从该list中获取不同的零钱面额。
代码如下:
(define us-coins (list 50 25 10 5 1)) (define uk-coins (list 100 50 20 10 5 2 1 0.5)) (define cn-coins (list 100 50 20 10 5 2 1)) (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 (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values)) (define (test-it) (cc 101 cn-coins))
SICP 习题 (2.19) 解题总结:重写零钱兑换程序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。