← 返回目录


SICP换零钱迭代方法实现,是如何写的?

学校≠教育≠技能;文凭溢价=80%信号传递+20%人力资本

11 👍 / 7 💬

问题描述

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))))
;这个是我找规律发现的。。。具体很难用口语表示。。。自己拿去用,上机调试。。。自己研究吧。。。

更新:改了一点小错误


← 返回目录