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

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 11k | 阅读时长 ≈ 10 分钟

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

学习资料：

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)

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

结果如下：

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

2.34(p80)

1
2
3
4
5
6
7
8
9
10
11
(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)

结果如下：

1
79

2.35(p81)

参考资料：

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

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

结果如下：

1
2
3
4
4
4
7
7

2.36(p81)

2.36_helper.scm：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(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)))))

测试函数：

1
2
3
4
5
6
7
8
(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)

结果如下：

1
(22 26 30)

2.37(p81)

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

结果如下：

1
2
3
4
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(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)

结果如下：

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

2.39(p82)

参考资料：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(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)

结果如下：

1
2
3
(25 16 9 4 1)
(25 16 9 4 1)
(25 16 9 4 1)

2.40(p84)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(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)

结果如下：

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

这里限制

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(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)

结果如下：

1
2
((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：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(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)))

测试代码：

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
(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
2
3
4
5
6
7
8
9
10
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(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)

结果如下：

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

该程序慢，是因为对于

1
(enumerate-interval 1 board-size)

中每个元素，都调用了

1
(queen-cols (- k 1))

所以总的时间复杂度为

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

文章作者:Doraemonzzz

发布时间:2021年01月10日 - 22:57:00

最后更新:2021年01月10日 - 22:57:32

原始链接:http://doraemonzzz.com/2021/01/10/计算机程序的构造和解释(SICP) 第2章 习题解析 Part3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

//