问题描述
scheme小菜,最近看书,看到换零钱这个问题,(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)))
x 想了好久都没想出来这道题迭代怎么写,有能讲解一下的大神吗?查了一下资料,有的说是动态规划,有的说是背包
我自己搞腾了一个,线性迭代,可能看起来有点迷,毕竟才刚开始学,废话不多说,上代码:
(define (change-count amount)
(cc 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (+ (/ amount 5) 1) 1 2 4))
;初始值设定,中间的(+(/ w 5) 1)是因为我找规律的时候发现硬币总数每加5,换硬币的方法才改变一次
(define (even? u)
(= (remainder u 2) 0))
;这个是用来判断偶数的
(define (cc a b c d e f g h i j k l m n o p q x y)
(cond ((= p q) a)
((even? q) (cc (- (+ y e j) o) a b c d e f g h i j k l m n p (+ q 1) x (+ y q 3)))
(else (cc (- (+ x e j) o) a b c d e f g h i j k l m n p (+ q 1) (+ x q 3) y))))
;这个是我找规律发现的。。。具体很难用口语表示。。。自己拿去用,上机调试。。。自己研究吧。。。
更新:改了一点小错误