SICP 第一章

大四的时候就听说《Structure and Interpretation of Computer Programs》这本书很不错，但一直没有时间拿来看看。正巧一个同事正在看这本书，于是我也来凑个热闹，大家可以一起讨论，不亦乐乎？

习题程序：http://files.getdropbox.com/u/1584769/chapter1.tar

1.5
(test 0 (p))
使用应用序求值时，会先对参数进行求值，即将这个表达式中的(p)展开为(p)，然后就死循环了，根本没有计算if表达式谓词的机会。

1.6
错：把if替换成为new-if之后就不是尾递归了，然后就堆栈溢出了
对：解释器的对于用户自定义函数的解释方式是应用序的，new-if也不能例外。
这样的后果就是new-if在被展开之前，它的参数就需要被计算，然后就死循环了。

1.7
试了一下，精度是16位。使用原有的good-enough?函数会出现的问题是当根的值达到16位这个极限的时候出现溢出。
当n很大的时候，根的平方减去n之后得到的是负数，那肯定小于给定的阈值咯。
使用新的good-enough?之后，对于很大的数和很小的数也能得出一个平方根的近似值。
当阈值（波动幅度）小于0.1%时，这个根的平方减去n的差值和n的比值大概在e-5这个数量级。

1.9
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b)))
)
(+ 4 5)的执行过程应该是这样的：
- (+ 4 5)
- (if (= 4 0)
- 5
- (inc (+ (dec 4) 5)))
- (inc (+ (dec 4) 5))
- (inc (+ 3 5))
- (inc (if (= 3 0)
- 5
- (inc (+ (dec 3) 5))))
- (inc (inc (+ (dec 3) 5)))
- (inc (inc (+ 2 5)))
- .
- .
- .
- (inc (inc (inc (inc (+ 0 5)))))
- (inc (inc (inc (inc 5))))
- (inc (inc (inc 6)))
- (inc (inc 7))
- (inc 8)
- 9
递归

(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
(+ 4 5)的执行过程应该是这样的：
- (+ 4 5)
- (if (= 4 0)
- 5
- (+ (dec 4) (inc 5)))
- (+ (dec 4) (inc 5))
- (+ 3 6)
- ...
- (+ 2 7)
- ...
- (+ 1 8)
- ...
- (+ 0 9)
- 9
迭代

1.10
(define (f n) (A 0 n)) == (f(x, y) = 2y)
(define (g n) (A 1 n)) == (g(x, y) = 2^y)
(define (h n) (A 2 n)) == (h(x, y) = 2^2^... (n次))

1.20
应用序：
(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
remainder执行了4次

正则序：
(gcd 206 40)
(gcd 40 (remainder 206 40)) ; gcd(40 6)
(if (= (remainder 206 40) 0) ; +1
40
(gcd (remainder 206 40) (remainder (remainder 206 40) 40)))
(gcd (remainder 206 40) (remainder (remainder 206 40) 40)) ; gcd(6 4)
(if (= (remainder (remainder 206 40) 40)) ; +2
(remainder 206 40)
(gcd (remainder (206 40) 40) (remainder (remainder 206 40) (remainder (remainder 206 40) 40))))
(gcd (remainder (206 40) 40) (remainder (remainder 206 40) (remainder (remainder 206 40) 40))) ; gcd (4 2)
(if (= 0 (remainder (remainder 206 40) (remainder (remainder 206 40) 40))) ; +4
(remainder (206 40) 40)
(gcd (remainder (remainder 206 40) (remainder (remainder 206 40) 40))
(remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40)) (remainder (remainder 206 40) 40))))
(gcd (remainder (remainder 206 40) (remainder (remainder 206 40) 40))
(remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40)) (remainder (remainder 206 40) 40)) ; gcd(2 0)
(if (= 0 (remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40)) (remainder (remainder 206 40) 40))) ; +7
(remainder (remainder 206 40) (remainder (remainder 206 40) 40)) ; +4
(gcd (remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40)) (remainder (remainder 206 40) 40))
(remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40))
(remainder (remainder (remainder 206 40) (remainder (remainder 206 40) 40)) (remainder (remainder 206 40) 40)))))
remainder执行了18次

1.21 - 1.28
由于guile的current-time只能精确到秒，程序无法得到实际运行的时间（只能得到0）。因此，这几个习题可能今后使用clisp或者MIT Scheme来实现。

1.34
(f, f)
-> (f, 2)
-> (2, 2)
出错：Wrong type to apply
把一个常数当作一个函数使用

1.36
启动数值a
a = 2.0时
不用平均阻尼：40步
使用平均阻尼：37步
a = 10.0时
不用平均阻尼：39步
使用平均阻尼：38步
a = 100.0时
不用平均阻尼：42步
使用平均阻尼：42步
a = 500.0时
不用平均阻尼：43步
使用平均阻尼：44步

1.37
a)和b)的解法都是偷懒的，因为D和N都等于1。这种办法到1.38就不行了。

1.41
(double)从表面上看是x2的关系，实际上是^2的关系，这从代码中可以看出来。
(define (double f)
(lambda (x) (f (f x))))
函数f第二次作用的对象是第一次作用的结果。
因此，由于(double double)函数的意义是将参数函数应用四次，那么当(double double)的参数是自身的时候，那就是4x4=16次了。

1.45
题目要求导出计算n次方根时使用平均阻尼的一般规律，可惜我没做出来。
在求五次方根时，两次平均阻尼虽然可以收敛，但是结果不正确。显然，收敛的方向出现了偏差。
求更加高次方根时，两次平均阻尼竟然都可以收敛，但是结果均不正确。
赶时间，没有仔细做下去。以后也许有机会。