计算机程序的构造和解释(SICP) 第1章 习题解析 Part1
这次回顾第一章的部分习题。
学习资料：
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://blog.csdn.net/sk__________________/article/details/12848597
https://sicp.readthedocs.io/en/latest
第1章
https://blog.csdn.net/sk__________________/article/details/12848597
https://sicp.readthedocs.io/en/latest
P13
1.1(p13)
10
10
(+ 5 3 4)
12
(- 9 1)
8
(/ 6 2)
3
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
19
(= a b)
#f
(if (and (> b a) (< b (* a b)))
b
a)
4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
16
(+ 2 (if (> b a) b a))
6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
161.2(p13)
前缀形式
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))
-37/1501.3(p13)
(define (max-two-sum-of-three a b c)
(if (> a b)
(if (> b c) (+ a b)
(+ a c))
(if (> a c) (+ a b)
(+ b c))
))
> (max-two-sum-of-three 1 2 3)
5
> (max-two-sum-of-three 1 3 2)
> (max-two-sum-of-three 2 1 3)
5
> (max-two-sum-of-three 2 3 1)
5
> (max-two-sum-of-three 3 2 1)
5
> (max-two-sum-of-three 3 1 2)
51.4(p13)
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))该函数等价于
1.5(p13)
参考资料：
https://blog.csdn.net/sk__________________/article/details/12848597
https://sicp.readthedocs.io/en/latest/chp1/5.html
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))正则序：将表达式展开后再带入求值。
应用序：先求参数的值，然后带入。
正则序：
(test 0 (p))
(if (= 0 0)
0
(p)))
0说明：由于(= 0 0)为true，所以(p)不会求值，于是直接得到0。
应用序：
(test 0 (p))
(if (= 0 0)
0
(p)))
(if (= 0 0)
0
(p)))
(if (= 0 0)
0
(p)))说明：应用序不断地对(p)求值，所以进入无限递归。
1.6(p16)
参考资料：
https://sicp.readthedocs.io/en/latest/chp1/6.html
会陷入无限递归，下面解释下具体原因。
首先利用大佬的例子解释两者的不同：
> (if #t (display "good") (display "bad"))
good
> (new-if #t (display "good") (display "bad"))
badgood可以看出new-if会计算两个分支，并不是短路操作，这是因为根据应用序规则，函数会对每个传入的参数求值。
回顾代码：
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (sqrt x)
(sqrt-iter 1.0 x))利用栈解释递归调用过程：
push guess1
push x
call sqrt-iter
push good-enough-res1
push guess1
push improve-x1
push x
call sqrt-iter
push good-enough-res2
push guess2
push improve-x2
...
call new-if可以看到形成了无限递归。
1.7(p17)
参考资料：
https://sicp.readthedocs.io/en/latest/chp1/7.html
测试案例：
非常小的数：
> (sqrt 0.00001)
0.03135649010771716
> (sqrt 0.0000001)
0.03125106561775382
> (sqrt 0.000000001)
0.03125001065624928对于非常小的数，阈值0.001过大，无法算出准确结果。
非常大的数：
> (sqrt 90000000000000000000000)
3e11
> (sqrt 9000000000000000000000000000000000)
break> 陷入死循环，打印结果可得guess的值为
9.48683298050514e16并且
> (improve 9.48683298050514e16 9000000000000000000000000000000000)
9.48683298050514e16表明：该结果的确是不动点，但是每次good-enough?的结果都为false，所以会陷入死循环。
本来以为死循环的原因是网上的精度问题，后来专门利用python程序测试了这点：
def sqrt_iter(guess, x):
print(guess)
if (good_enough(guess, x)):
return guess
else:
return sqrt_iter(improve(guess, x), x)
def improve(guess, x):
return (guess + x / guess) / 2
def good_enough(guess, x):
return abs(guess ** 2 - x) < 0.001
def sqrt_(x):
return sqrt_iter(1.0, x)
a = 9000000000000000000000000000000000
sqrt_(a)python程序依然会递归爆栈，所以应该不是精度的问题，查阅资料后终于找到原因。
更新式：
实际上是对如下方程使用牛顿法求解零点：
而牛顿法有收敛域，如果初始值不在收敛域中，那么该方法就不会收敛，所以对于非常大的$y$，由于这里初值是$1.0$，所以无法收敛。
改进：
(define (sqrt-iter last-guess x)
(let ((guess (improve last-guess x)))
(if (good-enough? last-guess guess)
guess
(sqrt-iter guess
x))))
(define (good-enough? last-guess guess)
(< (/ (abs (- last-guess guess)) guess) 0.00001))
; (define (good-enough? guess x)
; (display guess)
; (newline)
; (display (abs (- (square guess) x)))
; (newline)
; (< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (square x)
(* x x))
(define (sqrt x)
(sqrt-iter 1.0 x))备注：这里要使用let。
该方法可以保证递归结束，但是依然无法解决无法收敛的问题，因为该方法本质是依然是牛顿法，对于较大的参数，$1.0$和可能不在收敛域中，验证如下：
> (sqrt 9000000000000000000000000000000000)
9.48683298050514e16
> (* 9.48683298050514e16 9.48683298050514e16)
9.000000000000002e331.8(p17)
(define (cube-root-iter last-guess x)
(let ((guess (improve last-guess x)))
(if (good-enough? last-guess guess)
guess
(cube-root-iter guess
x))))
(define (good-enough? last-guess guess)
(< (/ (abs (- last-guess guess)) guess) 0.00001))
(define (improve y x)
(/ (+ (* 2 y) (/ x (* y y))) 3))
(define (cube-root x)
(cube-root-iter 1.0 x))1.9(p23)
计算：
(+ 4 5)过程1：
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))计算过程：
(+ 4 5)
;;(inc (+ (dec 4) 5))后续省略这个步骤
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9时间和空间都是线性的，所以是递归。
过程2：
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))计算过程：
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9时间是线性的，空间的常数级，所以是迭代。
1.10(p24)
函数定义（按照此顺序求值）：
计算：
(A 1 10)
(A 0 (A 1 9))
(* 2 (A 1 9))
(* 2 (A 0 (A 1 8)))
(* 2 (* 2 (A 1 8)))
...
2 ** 10 = 1024
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 16)
...
2 ** 16 = 65536
(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
2 ** 16 = 65536接着考虑如下几个过程：
1.
(define (f n) (A 0 n))显然
2.
(define (g n) (A 1 n))利用定义可得
3.
(define (h n) (A 2 n))利用定义可得
4.
(define (k n) (* 5 n n))利用定义可得
1.11(p27)
(define (f1 n)
(cond ((< n 4) n)
(else (+ (f1 (- n 1)) (* 2 (f1 (- n 2)) (* 3 (f1 (- n 3))))))))
(define (f2-iter a b c count)
(if (< count 4)
count
(f2-iter b c (+ c (* 2 b) (* 3 c)) (- count 1))))
(define (f2 n)
(f2-iter 1 2 3 n))
(define (test f1 f2 n)
(cond ((< (f1 n) (f2 n))
(display "error")
(newline))
((< (f1 n) (f2 n))
(display "error")
(newline))))1.12(p27)
定义过程：
pascal n m该过程计算$n$行第$m$个元素的值，其中$n\ge 0, 0\le m\le n$，代码如下：
(define (pascal n m)
(cond ((= m 0) 1)
((= m n) 1)
(else (+ (pascal (- n 1) m)
(pascal (- n 1) (- m 1))))))1.13(p28)
题目中没有定义$\gamma$，定义如下：
不难看出
用数学归纳法证明该结论。
当$n=0,1$时：
结论成立。
假设$n < k$时结论成立，那么$n=k$时：
所以$n=k$时结论也成立。
1.14(p29)
空间和时间复杂度都是指数级别。
1.15(p29)
(a)
(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))所以调用了5次p。
(b)
时间和空间复杂度都和将$a$变换到绝对值小于$0.1$的次数有关，所以时间和空间复杂度为$O(\log a)$。
值的回顾的习题
应用序，正则序：1.5, 1.6
牛顿法求零点的收敛问题：1.7