乐正

Actions speak louder than words.

Sicp-ex1-14

问题

请画出有关的树,展示1.2.2节的过程count-change在将11美分换成硬币时所产生的计算过 程。相对于被换成现金量的增加,这一计算过程的空间和步数增长的阶各是什么?

解答

回顾一下count-change:

count-change (count-coins.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (count-coins amount)
  (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)))

  (cc amount 5))

(count-change 11)产生的树形递归过程如下:

练习1.14

其空间和步数增长的阶正比于需要兑换的金额$n$,为$\Theta(n)$。

draft

« sicp-ex1-13 sicp-ex1-15 »

Comments