计算机程序的构造和解释(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)

1
2
3
4
5
6
7
8
(define (last-pair arr)
(if (null? (cdr arr))
(car arr)
(last-pair (cdr arr))))

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

结果如下:

1
34

2.18(p69)

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

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

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

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

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
(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的迭代过程如下:

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

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

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

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

几种方法的比较:

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

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

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

参考了网上的资料,核心是利用递归:

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
; (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:

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

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

结果如下:

1
2
3
4
5
6
7
8
9
3
12
12
#t
#t
#f
#t

2.30(p75)

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

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

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

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

文章作者:Doraemonzzz

发布时间:2021年01月03日 - 21:10:00

最后更新:2021年01月09日 - 20:55:05

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

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

//