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

这次回顾第一章剩余全部习题。

学习资料:

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

参考资料:

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

1.29(p39)

那么

从而得到代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))

(define (cube x) (* x x x))

(define (simpson f a b n)
(define h (/ (- b a) n))
(define (g a0)
(+ (f a0)
(* 4 (f (+ a0 h)))
(f (+ a0 (* 2 h)))))
(define (next a) (+ a (* 2 h)))
(* (sum g a next b)
(/ h 3)))

(display (simpson cube 0 1.0 100))
(newline)
(display (simpson cube 0 1.0 1000))
1
2
0.25000000000000044
0.2500000000000006

1.30(p40)

1
2
3
4
5
6
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))

1.31(p40)

定义

那么

定义

代码如下:

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
(define (product1 term a next b)
(if (> a b)
1
(* (term a)
(product1 term (next a) next b))))

(define (product2 term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (term a)))))
(iter a 1))

;; factorial
(define
(term a) a)
(define
(next a) (+ a 1))

(define (factorial product n)
(product term 1 next n))

(display "Factorial: ")
(newline)
(display "Product1: ")
(display (factorial product1 5))
(newline)
(display "Product2: ")
(display (factorial product2 5))
(newline)

;; pi
(define (square x)
(* x x))

(define (term 2k)
(/ (* 2k (+ 2k 2)) (square (+ 2k 1))))
(define (next 2k)
(+ 2k 2))

(define (pi product n)
(* 4 (product term 2.0 next (* 2 n))))

(display "Pi: ")
(newline)
(display "Product1: ")
(display (pi product1 100))
(newline)
(display "Product2: ")
(display (pi product2 100))

结果如下:

1
2
3
4
5
6
Factorial:
Product1: 120
Product2: 120
Pi:
Product1: 3.1493784731686008
Product2: 3.149378473168601

1.32(p40)

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
; 递归
(define (accumulate1 combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) (accumulate1 combiner null-value term (next a) next b))))

; 迭代
(define (accumulate2 combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result (term a)))))
(iter a null-value))

; sum
(define (sum term a next b)
(define (combiner a b)
(+ a b))
(define null-value 0)
(accumulate1 combiner null-value term a next b))

; prod
(define (product term a next b)
(define (combiner a b)
(* a b))
(define null-value 1)
(accumulate1 combiner null-value term a next b))

; test
; test for sum
(define (cube x) (* x x x))

(define (simpson f a b n)
(define h (/ (- b a) n))
(define (g a0)
(+ (f a0)
(* 4 (f (+ a0 h)))
(f (+ a0 (* 2 h)))))
(define (next a) (+ a (* 2 h)))
(* (sum g a next b)
(/ h 3)))

(display "Test for accumulate1 and sum:")
(newline)
(display (simpson cube 0 1.0 100))
(newline)
(display (simpson cube 0 1.0 1000))
(newline)

; test for prod
(define (square x)
(* x x))

(define (term 2k)
(/ (* 2k (+ 2k 2)) (square (+ 2k 1))))
(define (next 2k)
(+ 2k 2))

(define (pi product n)
(* 4 (product term 2.0 next (* 2 n))))

(display "Test for accumulate2 and product:")
(newline)
(display "Pi: ")
(display (pi product 100))

结果:

1
2
3
4
5
Test for accumulate1 and sum:
0.25000000000000044
0.2500000000000006
Test for accumulate2 and product:
Pi: 3.1493784731686008

1.33(p40)

对之前的代码稍微修改即可,这里(a)的函数包含上下界$a,b$:

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
;; prime?
(define (square a)
(* a a))

(define (smallest-divisor n)
(find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
(= (remainder b a) 0))

(define (prime? n)
(= n (smallest-divisor n)))

;; 1.33
(define (filtered-accumulate combiner filter null-value term a next b)
(cond ((> a b) null-value)
((filter a) (combiner (term a) (filtered-accumulate combiner filter null-value term (next a) next b)))
(else (filtered-accumulate combiner filter null-value term (next a) next b))))

; a
(define (prime-sum a b)
(define (combiner a b)
(+ a b))
(define (filter a)
(prime? a))
(define null-value 0)
(define (term a)
a)
(define (next a)
(+ a 1))
(filtered-accumulate combiner filter null-value term a next b))

; 2 + 3 + 5 + 7 = 17
(display "Test for a: ")
(display (prime-sum 2 10))
(newline)

; b
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

(define (n-prime-sum n)
(define (combiner a b)
(+ a b))
(define (filter a)
(= (gcd a n) 1))
(define null-value 0)
(define (term a)
a)
(define (next a)
(+ a 1))
(filtered-accumulate combiner filter null-value term 2 next n))

; 3 + 7 + 9 = 19
(display "Test for b: ")
(display (n-prime-sum 10))
(newline)

结果如下:

1
2
Test for a: 17
Test for b: 19

1.34(p44)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (square x)
(* x x))

(define (f g)
(g 2))

; 等价于(square 2)
(display (f square))
(newline)

; 等价于((lambda (z) (* z (+ z 1))) 2)
(display (f (lambda (z) (* z (+ z 1)))))
(newline)

; (f f)报错, 等价于(f 2)

结果如下:

1
2
4
6

1.35(p47)

求解方程可得:

所以结论成立。

对应代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
(define tolerance 0.00001)

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

(display (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))

结果如下:

1
1.6180327868852458

1.36(p47)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define tolerance 0.00001)

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess n)
(display n)
(display "th iteration: ")
(display guess)
(newline)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next (+ n 1)))))
(try first-guess 0))

(display "平均阻尼情形:")
(newline)
(fixed-point (lambda (x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.0)

(display "不用平均阻尼情形:")
(newline)
(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)

结果如下:

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
平均阻尼情形:
0th iteration: 2.0
1th iteration: 5.9828921423310435
2th iteration: 4.922168721308343
3th iteration: 4.628224318195455
4th iteration: 4.568346513136242
5th iteration: 4.5577305909237005
6th iteration: 4.555909809045131
7th iteration: 4.555599411610624
8th iteration: 4.5555465521473675
不用平均阻尼情形:
0th iteration: 2.0
1th iteration: 9.965784284662087
2th iteration: 3.004472209841214
3th iteration: 6.279195757507157
4th iteration: 3.759850702401539
5th iteration: 5.215843784925895
6th iteration: 4.182207192401397
7th iteration: 4.8277650983445906
8th iteration: 4.387593384662677
9th iteration: 4.671250085763899
10th iteration: 4.481403616895052
11th iteration: 4.6053657460929
12th iteration: 4.5230849678718865
13th iteration: 4.577114682047341
14th iteration: 4.541382480151454
15th iteration: 4.564903245230833
16th iteration: 4.549372679303342
17th iteration: 4.559606491913287
18th iteration: 4.552853875788271
19th iteration: 4.557305529748263
20th iteration: 4.554369064436181
21th iteration: 4.556305311532999
22th iteration: 4.555028263573554
23th iteration: 4.555870396702851
24th iteration: 4.555315001192079
25th iteration: 4.5556812635433275
26th iteration: 4.555439715736846
27th iteration: 4.555599009998291
28th iteration: 4.555493957531389
29th iteration: 4.555563237292884
30th iteration: 4.555517548417651
31th iteration: 4.555547679306398
32th iteration: 4.555527808516254
33th iteration: 4.555540912917957

1.37(p47)

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
(define (cont-frac1 n d k)
(define (cont-frac-iter i)
(if (= i k)
(/ (n k) (d k))
(/ (n i) (+ (d i) (cont-frac-iter (+ i 1))))))
(cont-frac-iter 1))

; (a) 找到k
(define tolerance 0.00001)
(define phi-1 (/ 1 1.6180327868852458))
(define (findk f n d)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (findk-iter k)
(if (close-enough? (f n d k) phi-1)
k
(findk-iter (+ k 1))))
(findk-iter 1))

; (a) 递归法
(display
(cont-frac1 (lambda (i) 1.0)
(lambda (i) 1.0)
10))
(newline)
(display "k is ")
(display
(findk cont-frac1 (lambda (i) 1.0)
(lambda (i) 1.0)))
(newline)

; (b) 迭代
(define (cont-frac2 n d k)
(define (cont-frac-iter i res)
(if (< i 1)
res
(cont-frac-iter (- i 1) (/ (n i) (+ (d i) res)))))
(cont-frac-iter k 0))

(display
(cont-frac2 (lambda (i) 1.0)
(lambda (i) 1.0)
10))

结果如下:

1
2
3
0.6179775280898876
k is 12
0.6179775280898876

1.38(p47)

$D_i$的计算公式如下:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (cont-frac n d k)
(define (cont-frac-iter i)
(if (= i k)
(/ (n k) (d k))
(/ (n i) (+ (d i) (cont-frac-iter (+ i 1))))))
(cont-frac-iter 1))

(define (d i)
(define r (remainder (- 2 i) 3))
(define k (/ (- i 2 r) 3))
(cond ((< i 3) i)
((= r 0) (* 2 (+ 1 k)))
(else 1)))

(display
(+ 2 (cont-frac (lambda (i) 1.0) d 10)))

结果如下:

1
2.7182817182817183

1.39(p48)

注意到有如下试试

所以取

然后利用之前的过程即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (cont-frac n d k)
(define (cont-frac-iter i)
(if (= i k)
(/ (n k) (d k))
(/ (n i) (+ (d i) (cont-frac-iter (+ i 1))))))
(cont-frac-iter 1))

(define (tan-cf x k)
(/ (cont-frac (lambda (i) (- (* x x)))
(lambda (i) (- (* 2 i) 1.0)) k)
(- x)))

(display (tan-cf 10 100))
(newline)
(display (tan 10))

结果如下:

1
2
0.6483608274590866
0.6483608274590866

1.40(p51)

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
; fixed-point
(define tolerance 0.00001)

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

; deriv
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
(define dx 0.00001)

; newton method
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))

; cubic
(define (cubic a b c)
(lambda (x)
(+ (* x x x) (* a x x) (* b x) c)))

(define (root a b c)
(newtons-method (cubic a b c) 1))

; test
(display (root -1 0 2))

结果如下:

1
-0.9999999999999872

1.41(p51)

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (double f)
(lambda (x) (f (f x))))

(define (inc x)
(+ x 1))

(display ((double inc) 5))
(newline)
(display (((double double) inc) 5))
(newline)
(display (((double (double double)) inc) 5))
(newline)
(display (((double (double (double double))) inc) 5))

结果如下:

1
2
3
4
7
9
21
261

结果说明:

定义

下面用数学归纳法证明:

其中

当$n=0$时,

所以结论成立。

假设$n=k$时结论成立,那么$n=k+1$时,

所以$n=k+1$时结论也成立。

1.42(p51)

1
2
3
4
5
6
7
8
9
10
11
(define (compose f g)
(lambda (x) (f (g x))))

(define (square x)
(* x x))

(define (inc x)
(+ x 1))

; test
(display ((compose square inc) 6))

结果如下:

1
49

1.43(p51)

利用递归即可:

1
2
3
4
5
6
7
8
9
10
11
12
(define (compose f g)
(lambda (x) (f (g x))))

(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))

(define (square x)
(* x x))

(display ((repeated square 2) 5))

结果如下:

1
625

1.44(p51)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (compose f g)
(lambda (x) (f (g x))))

(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))

(define (square x)
(* x x))

(define dx 0.00001)

(define (smooth f)
(lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

(define (nth-smooth f n)
((repeated smooth n) f))

; test
(display ((smooth square) 1.1))
(newline)
(display ((nth-smooth square 5) 1.1))

结果如下:

1
2
1.2100000000666669
1.2100000003333333

1.45(p52)

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
; fixed-point
(define tolerance 0.0000001)

(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))

; average-damp
(define (average-damp f)
(lambda (x) (average x (f x))))

(define (average x y)
(/ (+ x y) 2))

; repeated
(define (compose f g)
(lambda (x) (f (g x))))

(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))

; exp
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))

; k次阻尼
(define (kth-average-damp f k)
((repeated average-damp k) f))

; nth-root
(define (nth-root x n k)
(fixed-point (kth-average-damp (lambda (y) (/ x (expt y (- n 1)))) k) 1.0))

(display (nth-root 5 4 2))
(newline)

结果如下:

1
1.4953487812212205

1.46(p52)

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
(define (iterative-improve good-enough? improve)
(define (iterative-improve-iter x)
(if (good-enough? x)
x
(iterative-improve-iter (improve x))))
iterative-improve-iter)

; sqrt
(define (square x)
(* x x))

(define (average x y)
(/ (+ x y) 2))

(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.0001))
(define (improve guess)
(average guess (/ x guess)))
((iterative-improve good-enough? improve) 1.0))

(display (sqrt 2.0))
(newline)

; fixed-point
(define tolerance 0.00001)

(define (fixed-point f first-guess)
(define (good-enough? guess)
(< (abs (- (f guess) guess)) tolerance))
(define (improve guess)
(average guess (f guess)))
((iterative-improve good-enough? improve) 1.0))

(define (sqrt-fixed-point x)
(fixed-point (lambda (y) (average y (/ x y)))
1.0))
(display (sqrt-fixed-point 2.0))
(newline)

结果如下:

1
2
1.4142156862745097
1.4142047060743028

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

文章作者:Doraemonzzz

发布时间:2020年12月13日 - 19:19:00

最后更新:2020年12月13日 - 19:26:18

原始链接:http://doraemonzzz.com/2020/12/13/计算机程序的构造和解释(SICP) 第1章 习题解析 Part3/

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

//