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

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

学习资料：

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

http://community.schemewiki.org/?SICP-Solutions

http://community.schemewiki.org/?sicp

3.73(p239)

对应的关系为：

$$v=v_{0}+\frac{1}{C} \int_{0}^{t} i d t+R i$$

这一这里$i$是电流的含义，为了避免和整数搞混，这里将其替换为$x_i$，另外，根据题目中积分的定义，上式的实际含义为

$$v_i =v_0+\frac 1 C \sum_{j=1}^i x_j dt + Rx_i$$

取

$$v_0= 0,x_j = j,C=1,R=5, dt=0.5,j=0,\ldots$$

那么

$$\begin{aligned} v_i &= \frac 1 C \times \frac{i(i+1) dt}{2} +R i\\ &=\frac{i(i+1)}{4} + 5i \end{aligned}$$

在代码中，$v_0+\frac 1 C \sum_{j=1}^i x_j dt$利用积分表示，$ Rx_i$利用流表示，其中为了保证$i=0$时结论成立，在$Rx_i$对应的流中补充一个$0$，最后得到代码

(load "stream.scm")

(define (RC R C dt)
    (define (f input v0)
        (let ((scale-input (scale-stream input (/ 1 C))))
             (add-streams (integral scale-input v0 dt)
                          (scale-stream (cons-stream 0 input) R))))
    f)

; test
(define RC1 (RC 5 1 0.5))
(define input (integers-starting-from 1))
(define v0 0)
(define output (RC1 input v0))

(stream-head output 5)

结果如下：

1 ]=> (stream-head output 5)
;Value 13: (0 5.5 11.5 18. 25.)

3.74(p240)

代码：

(load "stream.scm")

(define (sign-change-detector a b)
    (cond ((and (>= a 0) (< b 0)) -1)
          ((and (>= b 0) (< a 0)) 1)
          (else 0)))

(define (zero-crossings sense-data)
    (stream-map sign-change-detector sense-data (stream-cdr sense-data)))

; test
(define sense-data
    (cons-stream 1
        (cons-stream 2
            (cons-stream -1
                (cons-stream -1
                    (cons-stream 2 integers))))))

(define res (zero-crossings sense-data))
(stream-head sense-data 6)
(stream-head res 6)

结果如下：

1 ]=> (stream-head sense-data 6)
;Value 13: (1 2 -1 -1 2 1)

1 ]=> (stream-head res 6)
;Value 14: (0 -1 0 1 0 0)

3.75(p240)

参考资料：

http://community.schemewiki.org/?sicp-ex-3.75

假设初始流为$\{a_i\}_{i=0}^{\infty}$，那么该方法的到的流为

$$\begin{aligned} b_0 & = \frac{a_0 + a_1} 2\\ b_i &= \frac{b_{i-1}+a_{i}}{2},i\ge 1 \end{aligned}$$

但是我们的目标是得到流

$$\begin{aligned} b_i &= \frac{a_{i}+a_{i+1}}{2},i\ge 0 \end{aligned}$$

在函数中记录$a_i$即可，这里人为补充$a_0=0$，代码如下

(load "stream.scm")
(load "helper.scm")

(define (make-zero-crossings input-stream last-value last-avpt)
    (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
        (cons-stream (sign-change-detector last-avpt avpt)
                    (make-zero-crossings (stream-cdr input-stream)
                                        (stream-car input-stream)
                                        avpt))))

(define (smooth input-stream)
    (scale-stream 
        (add-streams input-stream
            (cons-stream 0 input-stream))
        0.5))

(define (zero-crossings sense-data)
    (make-zero-crossings (stream-cdr sense-data)
                         (stream-car sense-data)
                         0))

; test
(define sense-data
    (cons-stream 1
        (cons-stream 2
            (cons-stream -1
                (cons-stream -1
                    (cons-stream 2 integers))))))


(define smooth-data (smooth sense-data))
(define res (zero-crossings sense-data))
(stream-head sense-data 6)
(stream-head smooth-data 6)
(stream-head res 6)

结果如下：

1 ]=> (stream-head sense-data 6)
;Value 13: (1 2 -1 -1 2 1)

1 ]=> (stream-head smooth-data 6)
;Value 14: (.5 1.5 .5 -1. .5 1.5)

1 ]=> (stream-head res 6)
;Value 15: (0 0 -1 1 0 0)

3.76(p240)

前一题中已经使用了这种观点，注意这里假设$a_0=0$，代码如下

(load "stream.scm")
(load "helper.scm")

(define (smooth input-stream)
    (scale-stream 
        (add-streams input-stream
            (cons-stream 0 input-stream))
        0.5))

; test
(define sense-data
    (cons-stream 1
        (cons-stream 2
            (cons-stream -1
                (cons-stream -1
                    (cons-stream 2 integers))))))

(define smooth-data (smooth sense-data))
(define res (zero-crossings smooth-data))
(stream-head sense-data 6)
(stream-head smooth-data 6)
(stream-head res 6)

结果如下

1 ]=> (stream-head sense-data 6)
;Value 13: (1 2 -1 -1 2 1)

1 ]=> (stream-head smooth-data 6)
;Value 14: (.5 1.5 .5 -1. .5 1.5)

1 ]=> (stream-head res 6)
;Value 15: (0 0 -1 1 0 0)

3.77(p242)

代码：

(load "stream.scm")

(define (solve f y0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (stream-map f y))
    y)

(define (integral delayed-integrand initial-value dt)
    (cons-stream initial-value
        (let ((integrand (force delayed-integrand)))
             (if (stream-null? integrand)
                   the-empty-stream
                   (integral (delay (stream-cdr integrand))
                             (+ (* dt (stream-car integrand))
                                initial-value)
                             dt)))
               ))

; test
(stream-ref (solve (lambda (y) y) 1 0.001) 1000)

结果如下：

1 ]=> ; test
(stream-ref (solve (lambda (y) y) 1 0.001) 1000)
;Value: 2.716923932235896

3.78(p242)

对于微分方程

$$\frac{\mathrm{d}^{2} y}{\mathrm{~d} t^{2}}-a \frac{\mathrm{d} y}{\mathrm{~d} t}-b y=0$$

取

$$\begin{aligned} a&= 1\\ b&=2 \end{aligned}$$

那么该微分方程对应的特征方程为

$$\begin{aligned} x^2-x-2&=0\\ (x-2)(x+1)&=0\\ x_1 &=2\\ x_2&= -1 \end{aligned}$$

所以通解为

$$y=pe^{2x}+qe^{-x}$$

取

$$\begin{aligned} y(0)&= 2\\ y'(0)&=1 \end{aligned}$$

可得

$$\begin{aligned} p&= 1\\ q&=1 \end{aligned}$$

所以

$$\begin{aligned} y&=e^{2x}+e^{-x}\\ y(0)&=2\\ y(1)&= e^2 + e^{-1} \end{aligned}$$

后续代码实验中应该符合上述讨论：

(load "stream.scm")
(load "delay-integral.scm")

(define (solve a b y0 dy0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (integral (delay ddy) dy0 dt))
    (define ddy (add-streams
                    (scale-stream dy a)
                    (scale-stream y b)))
    y)

; test
(stream-head (solve 1 2 2 1 0.001) 6)
(stream-ref (solve 1 2 2 1 0.001) 0)
(stream-ref (solve 1 2 2 1 0.001) 1000)

; 理论结果
(+ (exp 0) (exp 0))
(+ (exp 2) (exp -1))

结果如下：

1 ]=> ; test
(stream-head (solve 1 2 2 1 0.001) 6)
;Value 13: (2 2.001 2.002005 2.003015007 2.004030028017 2.005050070085031)

1 ]=> (stream-ref (solve 1 2 2 1 0.001) 0)
;Value: 2

1 ]=> (stream-ref (solve 1 2 2 1 0.001) 1000)
;Value: 7.742007815125568

1 ]=> ; 理论结果
(+ (exp 0) (exp 0))
;Value: 2

1 ]=> (+ (exp 2) (exp -1))
;Value: 7.756935540102093

3.79(p243)

利用前一题的结果来验证，取

$$f(x)=ax+b=x+2$$

得到代码

(load "stream.scm")
(load "delay-integral.scm")

(define (solve f y0 dy0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (integral (delay ddy) dy0 dt))
    (define ddy (stream-map f dy y))
    y)

; test
(define (function a b)
    (lambda (x y)
        (+ (* a x)
           (* b y))))

(define a 1)
(define b 2)
(define f (function a b))

(stream-head (solve f 2 1 0.001) 6)
(stream-ref (solve f 2 1 0.001) 0)
(stream-ref (solve f 2 1 0.001) 1000)

; 理论结果
(+ (exp 0) (exp 0))
(+ (exp 2) (exp -1))

结果如下

1 ]=> (stream-head (solve f 2 1 0.001) 6)
;Value 13: (2 2.001 2.002005 2.003015007 2.004030028017 2.005050070085031)

1 ]=> (stream-ref (solve f 2 1 0.001) 0)
;Value: 2

1 ]=> (stream-ref (solve f 2 1 0.001) 1000)
;Value: 7.742007815125568

1 ]=> ; 理论结果
(+ (exp 0) (exp 0))
;Value: 2

1 ]=> (+ (exp 2) (exp -1))
;Value: 7.756935540102093

3.80(p243)

参考资料：

http://community.schemewiki.org/?sicp-ex-3.80

首先验证等式$(\star)$

$$\begin{aligned} i_{R}&=i_{L}=-i_{C} \\ v_{C}&=v_{L}+v_{R} \end{aligned}$$

满足如下微分方乘

$$\begin{aligned} \frac{\mathrm{d} v_{c}}{\mathrm{d} t}&=-\frac{i_{L}}{C} \\ \frac{\mathrm{d} i_{L}}{\mathrm{d} t}&=\frac{1}{L} v_{c}-\frac{R}{L} i_{L} \end{aligned}$$

其中条件为

$$\begin{aligned} v_{R}&=i_{R} R \\ v_{L}&=L \frac{\mathrm{d} i_{L}}{\mathrm{d} t} \\ i_{C}&=C \frac{\mathrm{d} v_{C}}{\mathrm{d} t} \end{aligned}$$

首先将$\frac{\mathrm{d} v_{C}}{\mathrm{~d} t}$替换可得

$$\frac{i_C}{C} =-\frac{i_{L}}{C} \Leftrightarrow i_C =-i_L$$

显然等式$(\star)$满足该条件。

其次将$\frac{\mathrm{d} i_{L}}{\mathrm{d} t}$替换可得

$$\frac{1}{L}v_L=\frac{1}{L} v_{c}-\frac{R}{L} i_{L} \Leftrightarrow v_L + Ri_L = v_C$$

将

$$i_L= i_R$$

代入可得

$$v_L + Ri_L = v_c \Leftrightarrow v_L + Ri_R = v_c \Leftrightarrow v_L +v_R = v_C$$

显然等式$(\star)$满足该条件。

注意积分的定义要放在前面

3.81(p246)

参考资料：

http://community.schemewiki.org/?sicp-ex-3.81

一开始对此题的理解是传入一个command，导致比较大的困难，后来查了网上资料后发现大家都是给函数传入多个command，这样实现的难度就比较简单了：

(load "ch3support.scm")
(load "stream.scm")

(define (rand x)
    (define (dispatch number command)
        (cond ((eq? command 'generate) (rand-update number))
              ((eq? (car command) 'reset) (cadr command))
              (else (error "Unknown request" command))))
    (define (rand-stream commands) 
        (define random-numbers
            (cons-stream x
                (stream-map dispatch random-numbers commands)))
        random-numbers)
    rand-stream)

; test
(define random-init 7)
(define random-numbers (rand random-init))
(define commands
    (list->stream '(generate generate (reset 1) generate)))
(stream-head (random-numbers commands) 4)

结果如下

1 ]=> (stream-head (random-numbers commands) 4)
;Value 13: (7 88 116 1)

3.82(p246)

代码

(load "helper.scm")
(load "stream.scm")
(load "rand-stream.scm")

; 线性同余发生器参数
(define a 8121)
(define b 28411)
(define m 134456)

(define (rand-update x)
    (modulo (+ (* a x) b) m))

(define random-init 10)

(define random-numbers
    (cons-stream random-init
        (stream-map rand-update random-numbers)))

(define (experiment x1 x2 y1 y2)
    (let ((a (/ (abs (- x1 x2)) 2))
          (b (/ (abs (- y1 y2)) 2))
          (x0 (/ (+ x1 x2) 2))
          (y0 (/ (+ y1 y2) 2)))
         (define (f r1 r2)
            (let ((x (+ x0 (* (/ r1 (- m 1)) a)))
                  (y (+ y0 (* (/ r2 (- m 1)) b))))
                 (< (+ (/ (square (- x x0)) (square a))
                    (/ (square (- y y0)) (square b)))
                    1)))
         f))

; test
(define x1 0.0)
(define x2 10.0)
(define y1 10.0)
(define y2 30.0)
(define f (experiment x1 x2 y1 y2))

(define stream
    (map-successive-pairs f random-numbers))

(define pi
    (stream-map (lambda (p) (* 4 p))
        (monte-carlo stream 0 0)))

(stream-head pi 40)

结果如下

;Value 13: (4 4 4 4 16/5 8/3 16/7 5/2 8/3 12/5 24/11 7/3 32/13 18/7 12/5 5/2 44/17 8/3 52/19 14/5 20/7 32/11 68/23 3 76/25 40/13 28/9 22/7 92/29 16/5 100/31 13/4 36/11 54/17 16/5 29/9 116/37 60/19 124/39 16/5)