HeLU’s sicp answers
禾路的《计算机程序构造和解释》习题解答
2008 7—2008 9
“带着崇敬和赞美，将本书献给活在计算机里的神灵”
“你所掌握的，也是我认为并希望的，也就是智慧”
“让我们举起杯，祝福将智慧镶嵌在层层括号之间的lisp程序员”
…….
HeLU ：我非常感激地在大三暑假里面认真学习sicp，同时配合学习的还有TAOUP(《UNIX编程艺术》)，并且提供这份高质量的完全的答案,作为一名中国的学生，我清楚地知道我需要把习题答案写清楚，写明白，这是了解书中蕴藏智慧的第一步。我学习这本书的目的是为了能够深入了解计算机本质，增长作为一名计算机工程师的智慧；了解真正计算机的历史，激发创造的热情。我所学习到的所有关于schema的知识都将被用到我一直在编写的操作系统HinM(HinM is not Minix)中，也会被用到我平时的日常事物和编程事物中。
感谢那些在计算机的先驱和将计算机文化传播的程序员，你们激励了我。
HeLU(jsxyhelu@gmail.com)
EEI 2008-9-8
第一章
1.1
10,12,8,3,6,a,b,19,#f,4,16,6,16
（= a b ）的图形
1.2
(/(+ 5 4 (- 2 (- 3 (+ 6 4/5))))(* 3 (- 6 2)(- 2 7)))
或
如果写出
(/(+ 5 4 (- 2 (- 3 (+ 6 0.8))))(* 3 (- 6 2)(- 2 7)))则结果为
说明了在schema中，整数和小数是通过这样的方法区分的。
1.3
(define (square x) (* x x))
(define (fun1.3 a b c)
(+ (square (max a b))
(square(max (min a b) c))))
注意在这里max 和 min都是这个版本的schema提供的库函数。
1.4
如果a>0 结果为 a+b ,否则结果为a-b
1.5 本题的答案是：如果解释器采用正则序会死循环，如果是应用序会返回0 。
证明：
如果对于
(define (p) (p))
采用”正则序” 是无论如何也没法完全展开的，因为它会不断递归，所以“正则序”会死循环。 而对于“应用序”的实现，则会这样展开
(test 0 (p)) (if (= 0 0) 0 (p)) (if #t 0 (p)) 得到结果为： 0
证明完毕.
1.6
试验的例子的完整代码是这样的。
;;EXERCISE 1.6
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
会递归直到堆栈溢出。
我们知道 当 执行 else 的时候就会当条件不符合时直接跳入 else 并展开。 也就是象1.5 那样不断的用”正则序” 展开，所以死循环；做了以下实验，可以验证
(define (new-if pred thenc elsec) (cond (pred thenc) (else elsec))) (define (iter x y) (new-if (= x y) 0 (iter (+ x 1) y))) (define (iter-if x y) (if (= x y) 0 (iter-if (+ x 1) y))) (define (iter-cond x y) (cond ((= x y) 0) (else (iter-cond (+ x 1) y))))
对于 (iter 1 10), (iter-if 1 10), (iter-cond 1 10) 其中 iter 会 导致堆栈溢出，而 iter-cond 和 iter-if 并不会。
溢出提示
1.7
若假设精度为e
在程序中，判断取舍的代码为：
(< (abs (- (square guess) x)) e))
也就是说|guess^2(预测值)-x(真实值)|<e
也就是说 -e<guess^2(预测值)-x(真实值)<e 的时候是可以取的，显然，如果x 和guess^2都很小且都为正数，它们的差是不可能在这个区间之内，也就是不可能被取的，计算将始终循环。
对于特别大的数，由于浮点数在特别大时，离散性非常明显，相邻的两个数之间的差距会非常大，导致 |guess^2 - x| 始终 大于 e，计算便进入了 无限循环。 比如计算 (sqrt 1e300) 使用变化率改进后的代码如下：
(define (average x y)
(/ (+ x y) 2))
(define (square x) (* x x))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-new x)
(sqrt-new-iter x 1.0 x))
(define (sqrt-new-iter s1 s2 x)
(if (good-enough-new? s1 s2)
s2
(sqrt-new-iter s2 (improve s2 x) x)))
;改进的good-enough? 采用比值作为精度单位
(define (good-enough-new? s1 s2)
(< (/ (abs (- s1 s2)) s1) 0.001))
可以测算几个数，验证结果还是比较好的。
Welcome to DrScheme, version 4.0.2 [3m].
Language: R5RS; memory limit: 128 megabytes.
> (sqrt-new (square 1e150))
1.0000000000084744e+150
> (sqrt-new (square 1e-99))
1.0000000503202331e-099
1.8
采用1.7中的变化率检测方法
(define (cube-root x) (cube-root-iter x 1.0 x)) (define (cube-root-iter last-guess guess x) (if (enuf? last-guess guess) guess (cube-root-iter guess (improve guess x) x))) (define (enuf? x y) (< (/ (abs (- x y)) y) 0.001)) (define improve (lambda (y x) (/ (+ (/ x (* y y)) (* 2 y)) 3)))
1.9
很显然，第一个是递归的，第二个是迭代的。
(+ 4 5) (if (= 4 0) 5 (inc (+ (dec 4) 5)))
(inc (+ 3 5)) (inc (if (= 3 0) 5 (inc (+ 2 5)))) (inc (inc (if (= 2 0) 5 (inc (+ 1 5))))) (inc (inc (inc (if (= 1 0) 5 (inc (+ 0 5)))))) (inc (inc (inc (inc (if (= 0 0) 5 (inc (+ (dec 0) 5))))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6))) (inc (inc 7)) (inc 8) 9 (+ 4 5) (if (= 4 0) 5 (+ 3 6)) (if (= 3 0) 6 (+ 2 7)) (if (= 2 0) 7 (+ 1 8)) (if (= 1 0) 8 (+ 0 9)) (if (= 0 0) 9 (+ (dec 0) (inc 9))) 9
1.10
首先，可以写出这个函数的函数式：
0, y = 0; f(x,y) = 2y, x = 0; 2, y = 1; f(x-1, f(x, y-1));
那么，对于 f(0,n), n>=0 当 n >= 1 时， f(0,n) = 2n ， 而当 n = 0 时， f(0,0) = 0 = 2*0， 也满足 2n ， 故 f(0,n) = 2n, n>=0. 对于f(1,n), n>=1 当 n > 1 时，有 f(1,n) = f(0, f(1, n-1)) = 2*f(1,n-1), 设 f(1,n) = 2^n if n = 1, f(1,1) = 2 = 2^1 when n > 1, if f(1,n-1) = 2^(n-1) then f(1,n) = 2*f(1,n-1) = 2*(2^(n-1)) = 2^n 故 f(1,n) = 2^n, n>0. 对于f(2,n), n>0 if n > 1 ,then f(2,n) = f(1, f(2, n-1)) = 2^f(2,n-1), 设 f(2,n) = 2^(2^(... (n 个 2) if n = 1, then f(2,1) = 2 when n > 1, if f(2, n-1) = 2^(2^(... (n-1) then f(2,n) = 2^f(2,n-1) = 2^(2^( 这样我们对于 (A 1 10) = 2^10 = 1024, (A 2 4) = 2^(2^(2^2)) = 2^16 = 65536 而 (A 3 3) = (A 2 A(3 2)) = A(2 A(2 A(2 1))) = (A 2 4) = 2^16 = 65536 (f n) = (A 0 n) = 2n (g n) = (A 1 n) = 2^n (h n) = (A 2 n) = 2^(2^(... (n个2) --------------------------------------------- 在网上可以找到关于 Ackermann 函数的讨论，主要是针对这个双递归如何用迭代来实现，Ackermann 函数是 德国数学家W.Ackermann 在1928年提出的。