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

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

学习资料：

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

由于chez sheme对于stream的支持有些问题，所以这次作业将开发环境改为mit scheme，环境配置见SICP环境配置。

3.53(p230)

前五项分别为

1 2 4 8 16

所以通项为

$$a_n =2^n$$

验证结果：

(load "stream.scm")

(define s (cons-stream 1 (add-streams s s)))
(stream-head s 10)

运行结果：

1 ]=> (stream-head s 10)
;Value 13: (1 2 4 8 16 32 64 128 256 512)

3.54(p230)

定义

(define (mul-streams s1 s2)
  (stream-map * s1 s2))

整体代码

(load "stream.scm")

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

(define factorials 
    (cons-stream 1 
        (mul-streams
            factorials
                (stream-cdr integers))))

(stream-head factorials 5)

实验结果

1 ]=> (stream-head factorials 5)
;Value 13: (1 2 6 24 120)

3.55(p230)

代码

(load "stream.scm")

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

(define (partial-sums s)
    (define s1 
        (cons-stream 
            (stream-car s)
                (add-streams s1
                    (stream-cdr s))))
    s1)

(define stream (partial-sums integers))
(stream-head stream 10)

运行结果

1 ]=> (stream-head stream 10)
;Value 13: (1 3 6 10 15 21 28 36 45 55)

3.56(p230)

代码

(load "stream.scm")

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

(define S 
    (cons-stream 1
        (merge 
            (scale-stream S 2)
                (merge 
                    (scale-stream S 3)
                        (scale-stream S 5)))))

(stream-head S 10)

运行结果

1 ]=> (stream-head S 10)
;Value 13: (1 2 3 4 5 6 8 9 10 12)

3.57(p231)

注意前两项是已知的，所以计算第$n$项需要$n-2$次加法。

如果不使用memo-proc，那么需要重复计算，假设计算第$n$项需要的加法次数为$T_n$，那么

$$T_n = T_{n-1} +T_{n-2} + 1$$

令

$$G_n = T_n + 1$$

可得

$$G_n = G_{n-1} +G_{n-2}$$

所以$T_n$关于$n$是指数函数。

3.58(p232)

(expand 1 7 10)：

proc: (expand 1 7 10)
stream: (1)
proc: (expand 3 7 10)
stream: (1 4)
proc: (expand 2 7 10)
stream: (1 4 2)
proc: (expand 6 7 10)
stream: (1 4 2 8)
proc: (expand 4 7 10)
stream: (1 4 2 8 5)
proc: (expand 5 7 10)
stream: (1 4 2 8 5 7)
后续重复
proc: (expand 1 7 10)

(expand 3 8 10)：

proc: (expand 3 8 10)
stream: (3)
proc: (expand 6 8 10)
stream: (3 7)
proc: (expand 4 8 10)
stream: (3 7 5)
proc: (expand 0 8 10)
stream: (3 7 5 0)
proc: (expand 0 8 10)
stream: (3 7 5 0 0)
...

实验验证结果：

(load "stream.scm")

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))

(define s1 (expand 1 7 10))
(stream-head s1 10)
(define s2 (expand 3 8 10))
(stream-head s2 10)

运行结果：

1 ]=> (define s1 (expand 1 7 10))
;Value: s1

1 ]=> (stream-head s1 10)
;Value 13: (1 4 2 8 5 7 1 4 2 8)

1 ]=> (define s2 (expand 3 8 10))
;Value: s2

1 ]=> (stream-head s2 10)
;Value 14: (3 7 5 0 0 0 0 0 0 0)

分析：

通过运行后不难发现，该算法实际上是将(num * radix)按照den进制进行展开。

3.59(p231)

代码：

(load "stream.scm")

(define (integers-starting-from n)
    (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

; (a)
(define (integrate-series s)
    (div-streams s integers))

(define s1 (integrate-series integers))

(stream-head s1 10)

; (b)
(define exp-series
    (cons-stream 1 (integrate-series exp-series)))

(stream-head exp-series 10)

(define negative-ones 
    (cons-stream -1 negative-ones))

(define cosine-series
    (cons-stream 1 
        (mul-streams negative-ones 
            (integrate-series sine-series))))

(define sine-series
    (cons-stream 0 (integrate-series cosine-series)))

(stream-head cosine-series 10)

(stream-head sine-series 10)

实验结果：

1 ]=> (stream-head exp-series 10)
;Value 14: (1 1 1/2 1/6 1/24 1/120 1/720 1/5040 1/40320 1/362880)

1 ]=> (stream-head cosine-series 10)
;Value 15: (1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0)

1 ]=> (stream-head sine-series 10)
;Value 16: (0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880)

3.60(p232)

假设

$$\begin{aligned} A(x) & = \sum_{k=i}^{\infty} a_k x^k\\ B(x) & = \sum_{k=j}^{\infty} b_k x^k \end{aligned}$$

那么

$$\begin{aligned} A(x)B(x) & = a_i b_j + \left(\sum_{k=i + 1}^{\infty} a_k x^k \right) B(x) + A(x) \left(\sum_{k=j + 1}^{\infty} b_k x^k \right)- \left(\sum_{k=i + 1}^{\infty} a_k x^k \right)\left(\sum_{k=j + 1}^{\infty} a_k x^k \right)\\ \left(\sum_{k=i + 1}^{\infty} a_k x^k \right) B(x) & = a_{i+1} b_j x^{i+j+1} +\ldots\\ A(x)\left(\sum_{k=j + 1}^{\infty} b_k x^k \right) &= a_i b_{j+1} x^{i+j + 1} + \ldots\\ \left(\sum_{k=i + 1}^{\infty} a_k x^k \right)\left(\sum_{k=j + 1}^{\infty} a_k x^k \right) &= a_{i+1}b_{j+1}x^{i+j+2} +\ldots \end{aligned}$$

所以代码为

(load "stream.scm")
(load "series.scm")

(define (mul-series s1 s2)
    (cons-stream 
        (* (stream-car s1) (stream-car s2))
            (add-streams 
                (add-streams 
                    (mul-series (stream-cdr s1) s2)
                    (mul-series (stream-cdr s2) s1))
                (cons-stream 0 (scale-stream 
                    (mul-series (stream-cdr s1) (stream-cdr s2))
                        -1)))))

; test
(define s1 (mul-series cosine-series cosine-series))

(define s2 (mul-series sine-series sine-series))

(define s (add-streams s1 s2))

(stream-head s1 5)
(stream-head s2 5)
(stream-head s 5)

运行结果为

1 ]=> (stream-head s1 5)
;Value 13: (1 0 -1 0 1/3)

1 ]=> (stream-head s2 5)
;Value 14: (0 0 1 0 -1/3)

1 ]=> (stream-head s 5)
;Value 15: (1 0 0 0 0)

3.61(p232)

代码

(load "stream.scm")
(load "series.scm")

(define (inverse-series s)
    (define x
        (cons-stream 1
            (mul-series
                (scale-stream (stream-cdr s)
                    -1)
                x)))
    x)

; test
(define s1 (cons-stream 1 s1))
(define s2 (inverse-series s1))

(stream-head s1 5)
(stream-head s2 5)

运行结果

1 ]=> (stream-head s1 5)
;Value 13: (1 1 1 1 1)

1 ]=> (stream-head s2 5)
;Value 14: (1 -1 0 0 0)

补充说明：

这里取

$$s_1 =\frac 1 {1-x}=\sum_{i=0}^{\infty} x^i$$

3.62(p232)

设两个级数分别为$s_1,s_2$，我们要计算

$$s= \frac{s_1}{s_2}$$

不妨设$s_2$的常数项为$a$。

如果$s_2$的常数项为$0$，则报错；否则计算

$$s=\frac{s_1/a}{s_2/a}$$

那么利用之前的算法可以结算结果。

代码

(load "stream.scm")
(load "series.scm")

(define (div-series s1 s2)
    (let ((c (stream-car s2)))
         (if (= c 0)
             (error "Constant item of denominator is zero!" c)
             (mul-series
                (scale-stream s1 (/ 1 c))
                (inverse-series 
                    (scale-stream s2 (/ 1 c)))))))

; test
(define tan-series (div-series sine-series cosine-series))

(stream-head tan-series 10)

(define zero (cons-stream 0 zero))
(define test (div-series sine-series zero))

运行结果

1 ]=> (stream-head tan-series 10)
;Value 13: (0 1 0 1/3 0 2/15 0 17/315 0 62/2835)

补充：

注意正切函数泰勒展开的前几项：

$$\tan x = x +\frac{x^3}{3}+\frac{2x^5}{15} +\frac{17x^7}{315} + \ldots$$