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

距离上次更新已经 1541 天了，文章内容可能已经过时。

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

学习资料：

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.33(p80)

(define (map p sequence)
    (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(define (append seq1 seq2)
    (accumulate cons seq1 seq2))

(define (length sequence)
    (accumulate (lambda (x y) (+ y 1)) 0 sequence))

; test
(define evens (list 0 2 4 6 8))
(define odds (list 1 3 5 7))

; map
(define (square x)
    (* x x))
(newline)
(display (map square evens))

; append
(newline)
(display (append evens odds))

; length
(newline)
(display (length evens))
(newline)
(display (length odds))
(exit)

结果如下：

(0 4 16 36 64)
(1 3 5 7 0 2 4 6 8)
5
4

2.34(p80)

(load "helper.scm")

(define (horner-eval x coefficient-sequence)
    (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))
                0
                coefficient-sequence))

; test
(newline)
(display (horner-eval 2 (list 1 3 0 5 0 1)))
(exit)

结果如下：

79

2.35(p81)

参考资料：

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

(load "helper.scm")

(define (count-leaves t)
    ; 叶节点设置为1, 否则设置为0
    (accumulate (lambda (x y) (+ 1 y)) 0 
                (map (lambda (x) x) (enumerate-tree t))))

(define (count-leaves1 x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

; test
(define x (cons (list 1 2) (list 3 4)))
(define y (list (list 1 (list 2 3)) (list (list 4 5) (list 6 7))))
(newline)
(display (count-leaves x))
(newline)
(display (count-leaves1 x))
(newline)
(display (count-leaves y))
(newline)
(display (count-leaves1 y))
(exit)

结果如下：

4
4
7
7

2.36(p81)

2.36_helper.scm：

(define (first-element seqs)
    ; 取出seqs中每个list的第一个元素构成的list
    (if (null? seqs)
        '()
        (cons (caar seqs) (first-element (cdr seqs)))))

(define (remain-element seqs)
    ; 返回每个list中去除第一个元素构成的seqs
    (if (null? seqs)
        '()
        (cons (cdar seqs) (remain-element (cdr seqs)))))

(define (accumulate-n op init seqs)
    (if (null? (car seqs))
        '()
        (cons (accumulate op init (first-element seqs))
              (accumulate-n op init (remain-element seqs)))))

测试函数：

(load "helper.scm")
(load "2.36_helper.scm")

; test
(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
(newline)
(display (accumulate-n + 0 s))
(exit)

结果如下：

(22 26 30)

2.37(p81)

(load "2.36_helper.scm")

;; accumulate
(define (accumulate op initial sequence)
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence)))))

(define (dot-product v w)
    (accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
    (map (lambda (u) (dot-product u v)) m))

(define (transpose m)
    (accumulate-n cons '() m))

(define (matrix-*-matrix m n)
    (let ((cols (transpose n)))
        (map (lambda (v) (matrix-*-vector cols v)) m)))

; test
(define m (list (list 1 2 3 4) (list 5 6 7 8) (list 9 10 11 12)))
(define v (list 1 1 1 1))
(define u (list 1 1 1))
(define l (list u u u u))
(newline)
(display (dot-product (car m) v))
(newline)
(display (matrix-*-vector m v))
(newline)
(display (transpose m))
(newline)
(display (matrix-*-matrix m l))
(exit)

结果如下：

10
(10 26 42)
((1 5 9) (2 6 10) (3 7 11) (4 8 12))
((10 10 10) (26 26 26) (42 42 42))

2.38(p82)

(load "helper.scm")

(define (fold-left op initial sequence)
    (define (iter result rest)
        (if (null? rest)
            result
            (iter (op result (car rest))
                  (cdr rest))))
    (iter initial sequence))

(define fold-right accumulate)

; test
(newline)
(display (fold-right / 1 (list 1 2 3)))
(newline)
(display (fold-left / 1 (list 1 2 3)))
(newline)
(display (fold-right list '() (list 1 2 3)))
(newline)
(display (fold-left list '() (list 1 2 3)))
(exit)

结果如下：

3/2
1/6
(1 (2 (3 ())))
(((() 1) 2) 3)

2.39(p82)

参考资料：

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

(load "helper.scm")

(define (reverse1 sequence)
    (fold-right (lambda (x y) (cons x y)) '() sequence))

(define (reverse2 sequence)
    (fold-right (lambda (x y) (append (list x) y)) '() sequence))

(define (reverse3 sequence)
    (fold-left (lambda (x y) (cons y x)) '() sequence))

; test
(define x (list 1 4 9 16 25))
(newline)
(display (reverse1 x))
(newline)
(display (reverse2 x))
(newline)
(display (reverse3 x))
(exit)

结果如下：

(25 16 9 4 1)
(25 16 9 4 1)
(25 16 9 4 1)

2.40(p84)

(load "helper.scm")

(define (unique-pairs n)
    (flatmap (lambda (i)
                (map (lambda (j) (list i j))
                    (enumerate-interval 1 (- i 1))))
             (enumerate-interval 1 n)))

(define (prime-sum-pairs n)
    (map make-pair-sum (filter prime-sum? (unique-pairs n))))

; test
(newline)
(display (prime-sum-pairs 7))
(exit)

结果如下：

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

2.41(p84)

这里限制

$$i>j>k$$

代码如下：

(load "helper.scm")

; i > j
(define (unique-pairs n)
    (flatmap (lambda (i)
                (map (lambda (j) (list i j))
                    (enumerate-interval 1 (- i 1))))
             (enumerate-interval 1 n)))

(define (enu n s)
    ; (car arr): i, (cadr arr): j, lambda (arr): 生成(i, j, k)
    (map (lambda (arr) (append arr (list (- s (car arr) (cadr arr)))))
         ; 判断k < j, k > 0
         (filter (lambda (arr) 
                    (let ((k (- s (car arr) (cadr arr))))
                    (and (< k (cadr arr)) (< 0 k))))
                 (unique-pairs n))))

; test
(newline)
(display (enu 100 34))
(exit)

结果如下：

((13 11 10) (13 12 9) (14 11 9) (14 12 8) (14 13 7) (15 10 9) (15 11 8) (15 12 7) (15 13 6) (15 14 5) (16 10 8) (16 11 7) (16 12 6) (16 13 5) (16 14 4) (16 15 3) (17 9 8) (17 10 7) (17 11 6) (17 12 5) (17 13 4) (17 14 3) (17 15 2) (17 16 1) (18 9 7) (18 10 6) (18 11 5) (18 12 4) (18 13 3) (18 14 2) (18 15 1) (19 8 7) (19 9 6) (19 10 5) (19 11 4) (19 12 3) (19 13 2) (19 14 1) (20 8 6) (20 9 5) (20 10 4) (20 11 3) (20 12 2) (20 13 1) (21 7 6) (21 8 5) (21 9 4) (21 10 3) (21 11 2) (21 12 1) (22 7 5) (22 8 4) (22 9 3) (22 10 2) (22 11 1) (23 6 5) (23 7 
4) (23 8 3) (23 9 2) (23 10 1) (24 6 4) (24 7 3) (24 8 2) (24 9 1) (25 5 4) (25 6 3) (25 7 2) (25 8 1) (26 5 3) (26 6 2) (26 7 1) (27 4 3) (27 5 2) (27 6 1) (28 4 2) (28 5 1) (29 3 2) (29 4 1) (30 3 1) (31 2 1))

2.42(p84)

8-queens.scm：

(define empty-board '())

(define (get-kth-element k arr)
    (if (= k 1)
        (car arr)
        (get-kth-element (- k 1) (cdr arr))))

; 假设positions[:k-1]为safe, 判断positions[k]是否safe
(define (safe? k positions)
    (define d (get-kth-element k positions))
    (define (safe-iter index pos)
        (cond ((= index k) #t)
              ((or (= (car pos) d) 
                   (= (abs (- (car pos) d)) (abs (- k index)))) #f)
              (else (safe-iter (+ index 1) (cdr pos)))))
    (safe-iter 1 positions))

(define (adjoin-position new-row k rest-of-queens)
    (append rest-of-queens (list new-row)))

测试代码：

(load "helper.scm")
(load "8-queens.scm")

(define (queens board-size)
    (define (queen-cols k)
        (if (= k 0)
            (list empty-board)
            (filter
                (lambda (positions) (safe? k positions))
                (flatmap
                    (lambda (rest-of-queens)
                        (map (lambda (new-row)
                                (adjoin-position new-row k rest-of-queens))
                             (enumerate-interval 1 board-size)))
                    (queen-cols (- k 1))))))
    (queen-cols board-size))

; test
; get-kth-element test
(define arr (list 1 2 3 4))
(newline)
(display (get-kth-element 1 arr))
(newline)
(display (get-kth-element 4 arr))

; safe? test
(define p1 (list 1 2))
(define p2 (list 3 7 2 8 5 1 4 6))
(newline)
(display (safe? 2 p1))
(newline)
(display (safe? 8 p2))

; queens test
(newline)
(display (queens 8))
(exit)

结果如下：

1
4
#f
#t
((1 5 8 6 3 7 2 4) (1 6 8 3 7 4 2 5) (1 7 4 6 8 2 5 3) (1 7 5 8 2 4 6 3) (2 4 6 8 3 1 7 5) (2 5 7 1 3 8 6 4) (2 5 7 4 1 8 6 3) (2 6 1 7 4 8 3 5) (2 6 8 3 1 4 7 5) (2 7 3 6 8 5 1 4) (2 7 5 8 1 4 6 3) (2 8 6 1 3 5 7 4) (3 1 
7 5 8 2 4 6) (3 5 2 8 1 7 4 6) (3 5 2 8 6 4 7 1) (3 5 7 1 4 2 8 6) (3 5 8 4 1 7 2 6) (3 6 2 5 8 1 7 4) (3 6 2 7 1 4 8 5) (3 6 2 7 5 1 8 4) (3 6 4 1 8 5 7 2) (3 6 4 2 8 5 7 1) (3 6 8 1 4 7 5 2) (3 6 8 1 5 7 2 4) (3 6 8 2 4 
1 7 5) (3 7 2 8 5 1 4 6) (3 7 2 8 6 4 1 5) (3 8 4 7 1 6 2 5) (4 1 5 8 2 7 3 6) (4 1 5 8 6 3 7 2) (4 2 5 8 6 1 3 7) (4 2 7 3 6 8 1 5) (4 2 7 3 6 8 5 1) (4 2 7 5 1 8 6 3) (4 2 8 5 7 1 3 6) (4 2 8 6 1 3 5 7) (4 6 1 5 2 8 3 7) (4 6 8 2 7 1 3 5) (4 6 8 3 1 7 5 2) (4 7 1 8 5 2 6 3) (4 7 3 8 2 5 1 6) (4 7 5 2 6 1 3 8) (4 7 5 3 1 6 8 2) (4 8 1 3 6 2 7 5) (4 8 1 5 7 2 6 3) (4 8 5 3 1 7 2 6) (5 1 4 6 8 2 7 3) (5 1 8 4 2 7 3 6) (5 1 8 6 3 7 2 4) (5 2 
4 6 8 3 1 7) (5 2 4 7 3 8 6 1) (5 2 6 1 7 4 8 3) (5 2 8 1 4 7 3 6) (5 3 1 6 8 2 4 7) (5 3 1 7 2 8 6 4) (5 3 8 4 7 1 6 2) (5 7 1 3 8 6 4 2) (5 7 1 4 2 8 6 3) (5 7 2 4 8 1 3 6) (5 7 2 6 3 1 4 8) (5 7 2 6 3 1 8 4) (5 7 4 1 3 
8 6 2) (5 8 4 1 3 6 2 7) (5 8 4 1 7 2 6 3) (6 1 5 2 8 3 7 4) (6 2 7 1 3 5 8 4) (6 2 7 1 4 8 5 3) (6 3 1 7 5 8 2 4) (6 3 1 8 4 2 7 5) (6 3 1 8 5 2 4 7) (6 3 5 7 1 4 2 8) (6 3 5 8 1 4 2 7) (6 3 7 2 4 8 1 5) (6 3 7 2 8 5 1 4) (6 3 7 4 1 8 2 5) (6 4 1 5 8 2 7 3) (6 4 2 8 5 7 1 3) (6 4 7 1 3 5 2 8) (6 4 7 1 8 2 5 3) (6 8 2 4 1 7 5 3) (7 1 3 8 6 4 2 5) (7 2 4 1 8 5 3 6) (7 2 6 3 1 4 8 5) (7 3 1 6 8 5 2 4) (7 3 8 2 5 1 6 4) (7 4 2 5 8 1 3 6) (7 4 
2 8 6 1 3 5) (7 5 3 1 6 8 2 4) (8 2 4 1 7 5 3 6) (8 2 5 3 1 7 4 6) (8 3 1 6 2 5 7 4) (8 4 1 3 6 2 7 5))  

2.43(p85)

(load "helper.scm")
(load "8-queens.scm")

(define (queens board-size)
    (define (queen-cols k)  
        (if (= k 0)
            (list empty-board)
            (filter
                (lambda (positions) (safe? k positions))
                (flatmap
                    (lambda (new-row)
                        (map (lambda (rest-of-queens)
                                (adjoin-position new-row k rest-of-queens))
                             (queen-cols (- k 1))))
                    (enumerate-interval 1 board-size)))))
    (queen-cols board-size))

; test
(newline)
(display (queens 4))
(exit)

结果如下：

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

该程序慢，是因为对于

(enumerate-interval 1 board-size)

中每个元素，都调用了

(queen-cols (- k 1))

所以总的时间复杂度为

$$T\times \text{board-size}$$