计算机程序的构造和解释(SICP) 第3章 习题解析 Part7
这次回顾第三章第七部分习题。
学习资料：
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.63(p235)
该方法低效是因为每次都要重复计算
(sqrt-stream x)例如为了计算第二个元素，其计算方式为
(stream-map (lambda (guess)
(sqrt-improve guess x))
(sqrt-stream x)))
(stream-map (lambda (guess)
(sqrt-improve guess x))
(cons-stream 1 ...)))如果使用没有优化delay，那么如下实现每次调用时也会重复计算（因为不会查询是否计算过），
(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
guesses)))
guesses)3.64(p235)
代码：
(load "stream.scm")
(load "stream-app.scm")
(define (stream-limit s d)
(let ((s1 (stream-ref s 0))
(s2 (stream-ref s 1)))
(if (< (abs (- s1 s2)) d)
s2
(stream-limit (stream-cdr s) d))))
; test
(define (sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
(define x0 (sqrt 2 1))
x0
(define x1 (sqrt 2 0.1))
x1
(define x2 (sqrt 2 0.01))
x2
(exit)运行结果：
1 ]=> (define x0 (sqrt 2 1))
;Value: x0
1 ]=> x0
;Value: 1.5
1 ]=> (define x1 (sqrt 2 0.1))
;Value: x1
1 ]=> x1
;Value: 1.4166666666666665
1 ]=> (define x2 (sqrt 2 0.01))
;Value: x2
1 ]=> x2
;Value: 1.41421568627450973.65(p235)
代码：
(load "stream.scm")
(load "stream-app.scm")
(define (log2-stream n)
(cons-stream (/ 1.0 n)
(stream-map - (log2-stream (+ n 1)))))
(define log2-v1
(partial-sums (log2-stream 1)))
(define log2-v2
(euler-transform log2-v1))
(define log2-v3
(accelerated-sequence euler-transform log2-v1))
; test
(define log2 (log 2))
log2
(stream-head log2-v1 5)
(stream-head log2-v2 5)
(stream-head log2-v3 5)运行结果：
1 ]=> log2
;Value: .6931471805599453
1 ]=> (stream-head log2-v1 5)
;Value 13: (1. .5 .8333333333333333 .5833333333333333 .7833333333333332)
1 ]=> (stream-head log2-v2 5)
;Value 14: (.7 .6904761904761905 .6944444444444444 .6924242424242424 .6935897435897436)
1 ]=> (stream-head log2-v3 5)
;Value 15: (1. .7 .6932773109243697 .6931488693329254 .6931471960735491)3.66(p237)
通过举例不难得到序号的规律如下
1 2 4 6 8 10 12
3 5 9 13 17 21
7 11 19 27 35
15 23 39 54总结后得到如下规律：
- 第$(i,i)$项的序号为$2^{i}-1$
- 第$(i,i+1)$项的序号为$2^{i}-1 + 2^{i-1}=3\times 2^{i-1}-1$
- 第$i$行从第二项起为等差数列，公差为$2^i$
- 第$(i,j),j>i$项的序号为$3\times 2^{i-1}- 1 + (j- i-1)\times 2^i$
下面简单说下证明思路，首先根据定义得到$(1,1)$的序号为$1$，然后由于interleave是交错产生序列，所以可以简单找到$2,3$的位置：
1 2
3根据interleave的特点不难得到第一行剩余元素必然为偶数项的元素（注意这里强调的是偶数项）；因此根据递归定义，第二行及其之后的元素均为奇数，不妨设为$A_2$，那么根据递归定义，从二行开始的元素前三个元素为
3 5
7另一方面，注意$A_2$的公差为$2$，考虑第2行第$i$个元素，根据递归定义，其必然为$A_2$从小到大排列第$2\times (i-1)$个元素，所以第二行从第二项起的公差为$2\times 2=4$，由此得到第二行的通项，对其余每行进行分析即可得到全部通项。
3.67(p237)
代码：
(load "stream.scm")
(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(stream-map (lambda (x) (list x (stream-car t)))
(stream-cdr t)))
(pairs (stream-cdr s) (stream-cdr t)))))
; test
(define s (pairs integers integers))
(stream-head s 10)结果如下：
1 ]=> (stream-head s 10)
;Value 13: ((1 1) (1 2) (2 2) (2 1) (2 3) (1 3) (3 3) (3 1) (3 2) (1 4))3.68(p237)
参考资料：
http://community.schemewiki.org/?sicp-ex-3.68
https://github.com/kana/sicp/blob/master/ex-3.68.md
注意interleave是普通函数，所以当我们调用(pairs integers integers)时，其运行过程为
- (pairs integers integers)
- 调用interleave
- 运行(stream-map (lambda (x) (list (stream-car s) x)) t)
- 运行(pairs (stream-cdr s) (stream-cdr t))
因此会进入无穷递归。
代码：
(load "stream.scm")
(define (pairs s t)
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
t)
(pairs (stream-cdr s) (stream-cdr t))))
; test
(define s (pairs integers integers))
(stream-head s 10)运行结果：
1 ]=> ; test
(define s (pairs integers integers))
;Aborting!: maximum recursion depth exceeded3.69(p238)
思路说明，我们需要枚举
可以将其分解为如下几个部分
代码：
(load "stream.scm")
(load "helper.scm")
(define (interleaves s1 s2 s3)
(interleave s1
(interleave s2 s3)))
(define (triples s t u)
(cons-stream
(list
(stream-car s)
(stream-car t)
(stream-car u))
(interleaves
(stream-map
(lambda (x)
(list (stream-car s) (stream-car t) x))
(stream-cdr u))
(stream-map
(lambda (x)
(cons (stream-car s) x))
(pairs
(stream-cdr t)
(stream-cdr u)))
(triples
(stream-cdr s)
(stream-cdr t)
(stream-cdr u)))))
(define (pred arr)
(let ((i (car arr))
(j (cadr arr))
(k (caddr arr)))
(= (+ (square i)
(square j))
(square k))))
(define integers (integers-starting-from 1))
; test
(define s (triples integers integers integers))
(define pythagorean (stream-filter pred s))
(stream-head pythagorean 2)结果如下：
1 ]=> (stream-head pythagorean 2)
;Value 13: ((3 4 5) (6 8 10))3.70(p238)
参考资料：
http://community.schemewiki.org/?sicp-ex-3.70
网上参考了部分资料，都默认(car s1, car s2)为第一个元素，这样会有一些问题；但是由于无法使用3.68的方式定义函数，所以只能按照此方式编写函数。
代码：
(load "stream.scm")
(define (merge weight s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< (weight s1car) (weight s2car))
(cons-stream s1car (merge weight (stream-cdr s1) s2)))
((> (weight s1car) (weight s2car))
(cons-stream s2car (merge weight s1 (stream-cdr s2))))
(else
(cons-stream s1car
(cons-stream s2car
(merge weight (stream-cdr s1)
(stream-cdr s2))))))))))
(define (weighted-pairs weight s t)
(cons-stream
(list (stream-car s) (stream-car t))
(merge weight
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(weighted-pairs weight (stream-cdr s) (stream-cdr t)))))
(define (weight1 arr)
(let ((i (car arr))
(j (cadr arr)))
(+ i j)))
(define (weight2 arr)
(let ((i (car arr))
(j (cadr arr)))
(+ (* 2 i)
(* 3 j)
(* 5 i j))))
; test
; (a)
(define s1 (weighted-pairs weight1 integers integers))
(stream-head s1 10)
; (b)
(define s2 (weighted-pairs weight2 integers integers))
(stream-head s2 10)结果如下：
1 ]=> (stream-head s1 10)
;Value 13: ((1 1) (1 2) (1 3) (2 2) (1 4) (2 3) (1 5) (2 4) (3 3) (1 6))
1 ]=> (stream-head s2 10)
;Value 14: ((1 1) (1 2) (1 3) (2 2) (1 4) (1 5) (2 3) (1 6) (2 4) (1 7))3.71(p238)
参考资料：
http://community.schemewiki.org/?sicp-ex-3.71
代码：
(load "stream.scm")
(load "helper.scm")
(define (weight arr)
(let ((i (car arr))
(j (cadr arr)))
(+ (cube i) (cube j))))
(define s (weighted-pairs weight integers integers))
(define (ramanujan s)
(define (ramanujan-iter s d)
(let ((s1 (stream-car s))
(s2 (stream-car (stream-cdr s))))
(cond ((not (= (weight s1) d)) (ramanujan-iter (stream-cdr s) (weight s1)))
((= (weight s2) d) (ramanujan-iter (stream-cdr s) (weight s1)))
(else (cons-stream (weight s1) (ramanujan-iter (stream-cdr s) (weight s1)))))))
(ramanujan-iter s 0))
; test
(define Ramanujan (ramanujan s))
(stream-head Ramanujan 6)结果如下
1 ]=> (stream-head Ramanujan 6)
;Value 13: (1729 4104 13832 20683 32832 39312)函数解释：
- 对于函数(ramanujan-iter s d)，d表示当前处理的值。
- ((not (= (weight s1) d)) (ramanujan-iter (stream-cdr s) (weight s1)))对应(d, (a, … ))情形。
- ((= (weight s2) d) (ramanujan-iter (stream-cdr s) (weight s1)))对应(d, (d, d, …))情形。
- else对应(d, (d, d’, …))情形，该情形产生Ramanujan数。
3.72(p238)
这部分代码和前一题类似，只不过要增加一个计数变量。
代码：
(load "stream.scm")
(load "helper.scm")
(define (weight arr)
(let ((i (car arr))
(j (cadr arr)))
(+ (square i) (square j))))
(define (pythagorean s)
(define (pythagorean-iter s d cnt arr)
(let ((s1 (stream-car s))
(s2 (stream-car (stream-cdr s))))
(cond ((not (= (weight s1) d)) (pythagorean-iter (stream-cdr s) (weight s1) 1 (cons s1 '())))
((= (weight s2) d) (pythagorean-iter (stream-cdr s) (weight s1) (+ cnt 1) (cons s2 arr)))
((= cnt 3) (cons-stream
(list (weight s1) arr)
(pythagorean-iter (stream-cdr s) (weight s2) 1 (cons s2 '()))))
(else (pythagorean-iter (stream-cdr s) (weight s2) 1 (cons s2 '()))))))
(pythagorean-iter s 0 1 '()))
(define s (weighted-pairs weight integers integers))
(stream-head s 5)
(define s1 (pythagorean s))
; test
(stream-head s1 5)结果如下：
1 ]=> ; test
(stream-head s1 5)
;Value 14: ((325 ((10 15) (6 17) (1 18))) (425 ((13 16) (8 19) (5 20))) (650 ((17 19) (11 23) (5 25))) (725 ((14 23) (10 25) (7 26))) (845 ((19 22) (13 26) (2 29))))本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere