计算机程序的构造和解释(SICP) 第2章习题解析 Part2

这次回顾第二章第二部分习题。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

参考资料：

https://sicp.readthedocs.io/en/latest

2.17(p69)

(define (last-pair arr)
    (if (null? (cdr arr))
        (car arr)
        (last-pair (cdr arr))))

; test
(display (last-pair (list 23 72 149 34)))
(exit)

结果如下：

2.18(p69)

(load "helper.scm")

(define (reverse arr)
    (define n (length arr))
    (define (reverse-iter arr-iter i res)
        (if (= i n)
            res
            (reverse-iter (cdr arr-iter) (+ i 1) (cons (car arr-iter) res))))
    (reverse-iter arr 0 '()))

; test
(display (reverse (list 1 4 9 16 25)))
(exit)

结果如下：

1	(25 16 9 4 1)

2.19(p69)

(define (no-more? arr)
    (if (null? arr)
        #t
        #f))

(define (except-first-denomination arr)
    (cdr arr))

(define (first-denomination arr)
    (car arr))

(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)))))

; test
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(newline)
(display (cc 100 us-coins))
(newline)
(display (cc 100 uk-coins))
(exit)

结果如下：

1 2	292 104561

2.20(p69)

(define (judge a b)
    (= (remainder a 2) (remainder b 2)))

(define (same-parity x . arr)
    (define (same-parity-iter a b)
        (cond ((null? b) (list a))
              ((judge a (car b)) (cons a (same-parity-iter (car b) (cdr b))))
              (else (same-parity-iter a (cdr b)))))
    (same-parity-iter x arr))

; test
(newline)
(display (same-parity 1 2 3 4 5 6 7))
(newline)
(display (same-parity 2 3 4 5 6 7))
(exit)

结果如下：

1 2	(1 3 5 7) (2 4 6)

2.21(p71)

(load "helper.scm")

(define (square-list1 items)
    (if (null? items)
        '()
        (cons (square (car items)) (square-list1 (cdr items)))))

(define (square-list2 items)
    (map square items))

; test
(newline)
(display (square-list1 (list 1 2 3 4)))
(newline)
(display (square-list2 (list 1 2 3 4)))
(exit)

结果如下：

1 2	(1 4 9 16) (1 4 9 16)

2.22(p72)

(load "helper.scm")

(define (square-list1 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items '()))

(define (square-list2 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items '()))

; test
(newline)
(display (square-list1 (list 1 2 3 4)))
(newline)
(display (square-list2 (list 1 2 3 4)))
(exit)

结果测试：

1 2	(16 9 4 1) ((((() . 1) . 4) . 9) . 16)

方法1的迭代过程如下：

things answer
(1 2 3 4) '()
(2 3 4) (1)
(3 4) (4 1)
(4) (9 4 1)
'() (16 9 4 1)

方法2 cons的一个元素是列表，但我们希望的是一个数。

2.23(p72)

参考资料：

https://sicp.readthedocs.io/en/latest/chp2/23.html

(define (for-each proc arr)
    (cond ((not (null? arr))
           (proc (car arr))
           (for-each proc (cdr arr)))))

; test
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
(exit)

结果如下：

1
2
3

57
321
88

2.24(p73)

1 2	> (list 1 (list 2 (list 3 4))) (1 (2 (3 4)))

2.25(p74)

(define a (list 1 3 (list 5 7) 9))
(newline)
(display (car (cdr (car (cdr (cdr a))))))

(define b (list (list 7)))
(newline)
(display (car (car b)))

(define c (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(newline)
(display (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr c)))))))))))))

(exit)

结果如下：

1
2
3

7
7
7

2.26(p74)

(load "helper.scm")

(define x (list 1 2 3))
(define y (list 4 5 6))

; test
(newline)
(display (append x y))
(newline)
(display (cons x y))
(newline)
(display (list x y))
(exit)

结果如下：

1
2
3

(1 2 3 4 5 6)
((1 2 3) 4 5 6)
((1 2 3) (4 5 6))

2.27(p74)

参考资料：

https://sicp.readthedocs.io/en/latest/chp2/27.html

几种方法的比较：

(load "helper.scm")

(define x (list (list 1 2) (list 3 4)))
(define y (list (list 1 2) (list 3 4) (list 5 6)))

(define (deep-reverse1 arr)
    (cond ((null? arr) '()) ;空节点
          ((not (pair? arr)) arr) ;叶节点
          ((null? (cdr arr)) (deep-reverse1 (car arr)))
          (else (list (deep-reverse1 (cdr arr)) (deep-reverse1 (car arr))))))

(define (deep-reverse2 arr)
    (define (deep-reverse-iter arr-iter res)
        (if (null? arr-iter) res
            (deep-reverse-iter (cdr arr-iter) (cons (car arr-iter) res))))
    (deep-reverse-iter arr '()))

(define (deep-reverse3 arr)
    (define (deep-reverse-iter arr-iter res)
        (if (null? arr-iter) res
            (deep-reverse-iter (cdr arr-iter) 
                               (cons (if (pair? (car arr-iter)) (deep-reverse3 (car arr-iter))
                                         (car arr-iter)) res))))
    (deep-reverse-iter arr '()))

; test
(newline)
(display y)
(newline)
(display (reverse y))
(newline)
(display (deep-reverse1 y))
(newline)
(display (deep-reverse2 y))
(newline)
(display (deep-reverse3 y))
(exit)

结果如下：

((1 2) (3 4) (5 6))
((5 6) (3 4) (1 2))
(((6 5) (4 3)) (2 1))
((5 6) (3 4) (1 2))
((6 5) (4 3) (2 1))

2.28(p74)

参考资料：

https://sicp.readthedocs.io/en/latest/chp2/28.html

(load "helper.scm")

(define (fringe tree)
    (cond ((null? tree) '()) ;空节点
          ((not (pair? tree)) (list tree)) ;叶节点
          (else (append (fringe (car tree)) (fringe (cdr tree))))))

(define x (list (list 1 2) (list 3 4)))
(newline)
(display (fringe x))
(newline)
(display (fringe (list x x)))
(exit)

结果如下：

1 2	(1 2 3 4) (1 2 3 4 1 2 3 4)

2.29(p74)

参考资料：

https://sicp.readthedocs.io/en/latest/chp2/29.html

参考了网上的资料，核心是利用递归：

; (load "2.29_1.scm")
(load "2.29_2.scm")

; (b)
(define (branch-weight branch)
    ; 如果不是mobile, 则直接返回weight; 否则返回total weight
    (if (is-mobile? branch)
        (total-weight (branch-structure branch))
        (branch-structure branch)))

(define (is-mobile? branch)
    (pair? (branch-structure branch)))

(define (total-weight mobile)
    (+ (branch-weight (left-branch mobile))
       (branch-weight (right-branch mobile))))

; (c)
(define (torque branch)
    ; 计算力矩
    (* (branch-length branch) (branch-weight branch)))

(define (branch-balance branch)
    ; 如果不是mobile则返回true, 否则调用mobile-balance
    (if (is-mobile? branch)
        (mobile-balance (branch-structure branch))
        #t))

(define (mobile-balance mobile)
    (let ((l (left-branch mobile))
          (r (right-branch mobile)))
         (and (branch-balance l)
              (branch-balance r)
              (= (torque l) (torque r)))))

; test
(define l1 (make-branch 4 5))
(define l2 (make-branch 5 4))
(define l3 (make-branch 1 2))
(define l4 (make-branch 2 1))
(define m1 (make-mobile l1 l2))
(define m2 (make-mobile l3 l4))
(define m3 (make-mobile (make-branch 1 m1) (make-branch 1 m2)))
(define m4 (make-mobile (make-branch 1 m1) (make-branch 3 m2)))

; (a)
(newline)
(display (total-weight m1))
(newline)
(display (total-weight m2))
(newline)
(display (total-weight m3))
(newline)
(display (total-weight m4))

; (b)
(newline)
(display (mobile-balance m1))
(newline)
(display (mobile-balance m2))
(newline)
(display (mobile-balance m3))
(newline)
(display (mobile-balance m4))
(exit)

2.29_1.scm：

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

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

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

(define (right-branch mobile)
    (cadr mobile))

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

(define (branch-structure branch)
    (cadr branch))

2.29_2.scm：

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

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

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

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

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

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

结果如下：

9
3
12
12
#t
#t
#f
#t

2.30(p75)

(load "helper.scm")

(define (square-tree1 tree)
    (cond ((null? tree) '())
          ((not (pair? tree)) (square tree))
          (else (cons (square-tree1 (car tree))
                      (square-tree1 (cdr tree))))))

(define (square-tree2 tree)
    (map (lambda (sub-tree)
                 (if (pair? sub-tree)
                     (square-tree2 sub-tree)
                     (square sub-tree)))
          tree))

; test
(define tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(newline)
(display (square-tree1 tree))
(newline)
(display (square-tree2 tree))
(exit)

结果如下：

1 2	(1 (4 (9 16) 25) (36 49)) (1 (4 (9 16) 25) (36 49))

2.31(p76)

(load "helper.scm")

(define (tree-map proc tree)
    (cond ((null? tree) '())
          ((not (pair? tree)) (proc tree))
          (else (cons (tree-map proc (car tree))
                      (tree-map proc (cdr tree))))))

(define (square-tree tree) (tree-map square tree))

; test
(define tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(newline)
(display (square-tree tree))
(exit)

结果如下：

1	(1 (4 (9 16) 25) (36 49))

2.32(p76)

思路是对rest中每个元素（集合）添加(car s)

(load "helper.scm")


(define (subsets s)
    (if (null? s)
        (list '())
        (let ((rest (subsets (cdr s))))
             (append rest (map (lambda (subset) (cons (car s) subset)) rest)))))

; test
(define set (list 1 2 3))
(newline)
(display (subsets set))
(exit)

结果如下：

1	(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

值的回顾的习题

2.23, 2.26, 2.27, 2.29, 2.31