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

记

$$x_{2k}=y_{2k} + 4y_{2k+1} + y_{2k+2}$$

那么

$$\begin{aligned} &\frac{h}{3}\left[y_{0}+4 y_{1}+2 y_{2}+4 y_{3}+2 y_{4}+\cdots+2 y_{n-2}+4 y_{n-1}+y_{n}\right]\\ =& \frac h3 \sum_{k=0}^{n/2} x_{2k} \end{aligned}$$

从而得到代码：

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

0.25000000000000044
0.2500000000000006

1.30(p40)

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

定义

$$x_{2k}= \frac{(2k)\times (2k + 2)}{(2k + 1)^2}$$

那么

$$\pi = 4\times \prod_{k=1}^{\infty} x_{2k}$$

定义

$$\pi_n =4\times \prod_{k=1}^{n} x_{2k}$$

代码如下：

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

结果如下：

Factorial:
Product1: 120
Product2: 120
Pi:
Product1: 3.1493784731686008
Product2: 3.149378473168601

1.32(p40)

; 递归
(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))

结果：

Test for accumulate1 and sum:
0.25000000000000044
0.2500000000000006
Test for accumulate2 and product:
Pi: 3.1493784731686008

1.33(p40)

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

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

结果如下：

Test for a: 17
Test for b: 19

1.34(p44)

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

结果如下：

4
6

1.35(p47)

求解方程可得：

$$\begin{aligned} x&= 1 +\frac 1 x\\ x^2 -x -1&=0\\ x& =\frac{1\pm \sqrt 5}{2} \end{aligned}$$

所以结论成立。

对应代码：

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

1.36(p47)

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

结果如下：

平均阻尼情形:
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)

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

结果如下：

0.6179775280898876
k is 12
0.6179775280898876

1.38(p47)

$D_i$的计算公式如下：

$$D_i=\begin{cases} i &i\le 2\\ 2k+2& i =3k+2, k\ge 1\\ 1& 其他 \end{cases}$$

代码如下：

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

结果如下：

2.7182817182817183

1.39(p48)

注意到有如下试试

$$\begin{aligned} \tan x &=\frac{x}{1-\frac{x^{2} }{3-\frac{x^{2} }{5-\ddots} }}\\ &= \frac{-x^2}{1-\frac{x^{2} }{3-\frac{x^{2} }{5-\ddots} }} / (-x) \end{aligned}$$

所以取

$$\begin{aligned} N_i &= -x^2\\ D_i&= 2i-1 \end{aligned}$$

然后利用之前的过程即可，代码如下：

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

结果如下：

0.6483608274590866
0.6483608274590866

1.40(p51)

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

结果如下：

-0.9999999999999872

1.41(p51)

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

结果如下：

7
9
21
261

结果说明：

定义

$$d_n =\begin{cases} \mathrm {double} & n = 0\\ (\mathrm {double}\ d_{n-1} )&n \ge 1 \end{cases}$$

下面用数学归纳法证明：

$$(d_n \ f) = f^{2^{2^n} }$$

其中

$$(f^n\ x) =\begin{cases} \mathrm (f\ x) & n = 1\\ (f \ (f^{n -1}\ x ))&n \ge 2 \end{cases}$$

当$n=0$时，

$$((d_n \ f)\ x)=((\mathrm{double} \ f)\ x)= (f \ (f\ x)) = (f^{2}\ x)$$

所以结论成立。

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

$$\begin{aligned} ((d_k \ f)\ x) &=((d_k \ f)\ x) \\ &= (((\mathrm{double}\ d_{k-1} )\ f)\ x)\\ &= ((d_{k-1}\ (d_{k-1} \ f))\ x)\\ &= ((d_{k-1}\ f^{2^{2^{k-1} }})\ x)\\ &=( {(f^{2^{2^{k-1} }})}^{2^{2^{k-1} }}\ x)\\ &=( {f^{2^{2^{k-1} }\times 2^{2^{k-1} }} }\ x)\\ &=(f^{ {2^{2^k} }}\ x) \end{aligned}$$

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

1.42(p51)

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

结果如下：

49

1.43(p51)

利用递归即可：

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

结果如下：

625

1.44(p51)

(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.2100000000666669
1.2100000003333333

1.45(p52)

; 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.4953487812212205

1.46(p52)

(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.4142156862745097
1.4142047060743028