乐正

Actions speak louder than words.

Sicp-ex2-29

问题

一个二叉活动体由两个分支组成,一个是左分支,另一个是右分支。每个分支是一个具有确 定长度的杆,上面或者吊着一个重量,或者吊着另一个活动体。我们可以用复合数据对象表 示这种二叉活动体,将它通过其两个分支构造起来(例如,使用list):

1
2
(define (make-mobile left right)
  (list left right))

分支可以从一个length(它应该是一个数)再加上一个structure构造出来,这个structure 或者是一个数(表示一个简单重量),或者是另一个活动体:

1
2
(define (make-branch length structure)
  (list length structure))

a) 请写出对应的选择函数left-branchright-branch,它们分别返回活动体的两个分 支。还有branch-lengthbranch-structure。它们返回一个分支上的成分。

b) 用你的选择函数定义过程total-weight,它返回一个活动体的总重量。

c) 一个活动体称为是平衡的,如果其左分支的力矩等于其右分支的力矩(也就是说,如果 其左杆的长度乘以吊在杆上的重量,等于这个活动体右边同样的乘积),而且在其每个分支 上吊着的子活动体也平衡。请设计一个过程,它能检查一个二叉活动体是否平衡。

d) 假定我们改变活动体的表示,采用下面的构造方式:

1
2
3
4
5
(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))

你需要对自己的程序做多少修改,才能将它改变为使用这种新表示?

解答

(b)小题的解题思路和练习2.28一样,累加活动体的左右分支重量。

(c)小题的解题思路是:

  • (1) 判断当前活动体是否平衡,如果平衡,跳到(2);否则返回#f
  • (2) 将活动体左右分支当做新的活动体,回到(1)
  • (3) 如果新传递到(1)中的分支下不是一个活动体,返回#t
  • (4) 否则循环,直到所有活动体都被判断
练习2.29 (ex2-29.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
;; Happy hacking Yuez - Emacs ♥ you!

(define (make-mobile left right)
  (list left right))

(define (make-branch length structure)
  (list length structure))

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (car (cdr mobile)))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

(define (total-weight mobile)
  (define (iter branch weight)
    (cond ((null? branch) weight)
          ((not (pair? branch))
           (+ branch weight))
          (else (iter (branch-structure (left-branch branch))
                      (iter (branch-structure (right-branch branch)) weight)))))
  (iter mobile 0))

(define (balance-mobile? mobile)
  (define (moment branch)
    (* (branch-length branch)
       (total-weight (branch-structure branch))))

  (cond ((not (pair? mobile)) #t)
        ((= (moment (left-branch mobile))
            (moment (right-branch mobile)))
         (and (balance-mobile? (branch-structure (left-branch mobile)))
              (balance-mobile? (branch-structure (right-branch mobile)))))
        (else #f)))

如果采用(d)小题的声明方式,那么需要对right-branchbranch-structure进行更改 后,程序能正常运行:

1
2
3
4
5
(define (right-branch mobile)
  (cdr mobile))

(define (branch-structure mobile)
  (cdr mobile))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
;; 测试 total-weight
(define mobile (make-mobile (make-branch 3
                                         (make-mobile (make-branch 5 13)
                                                      (make-branch 3 18)))
                            (make-branch 9
                                         (make-mobile (make-branch 4 18)
                                                      (make-branch 3 6)))))
;Value: mobile

(total-weight mobile)
;Value: 55

(total-weight (make-mobile (make-branch 3 4)
                           (make-branch 4 10)))
;Value: 14

;; 测试 balance-mobile?
(define bm (make-mobile (make-branch 3 4)
                        (make-branch 2 6)))
;Value: bm

(balance-mobile? bm)
;Value: #t

(define nbm (make-mobile (make-branch 3 5)
                         (make-branch 3 4)))
;Value: nbm

(balance-mobile? nbm)
;Value: #f

(define mobile (make-mobile (make-branch 3
                                         (make-mobile (make-branch 3 4)
                                                      (make-branch 2 6)))
                            (make-branch 3
                                         (make-mobile (make-branch 2 6)
                                                      (make-branch 3 4)))))
;Value: mobile

(balance-mobile? mobile)
;Value: #t

(define mobile (make-mobile (make-branch 4
                                         (make-mobile (make-branch 3 4)
                                                      (make-branch 2 6)))
                            (make-branch 2
                                         (make-mobile (make-branch 2 6)
                                                      (make-branch 3 4)))))
;Value: mobile

(balance-mobile? mobile)
;Value: #f

;; 测试小题(d)
(define mobile (make-mobile (make-branch 3 4)
                            (make-branch 4 3)))
;Value: mobile

(total-weight mobile)
;Value: 7

(balance-mobile? mobile)
;Value: #t

(right-branch mobile)
;Value 23: (4 . 3)

(left-branch mobile)
;Value 24: (3 . 4)

(branch-length (left-branch mobile))
;Value: 3

(branch-structure (left-branch mobile))
;Value: 4

draft

« sicp-ex2-28 sicp-ex2-30 »

Comments