SICP 第二章（上）

第二章比较长，习题也多很多，所以还是分两次贴比较好。完成这一章的习题要花一些功夫，比如需要DrScheme来画2.2.4那一节的小人儿，2.5节也需要额外代码的支持。习题做到最后，代码都很长了，一个文件里有三百多行。Scheme代码的可读性和条理性在没有注释的情况下比其他语言要差多了，希望下一章能够解决这个问题。

2.6
这个题目比较好玩，使用到了Church Numerals。
第一眼看到这个问题马上让我想起了离散数学，因为他们都定义了一套运算体系。
上wiki查了一下Church Numerals，说的很详细，让我理解了一些基本概念。
one和two的定义用zero和add-1可以比较容易的推导出来。
看了wiki上的说明以及one和two的定义可以看出，n的意义就是对参数x应用n次参数f。
知道这个再写加法就简单了，特别是add-1可以看作n和one的加法。我基本是像搭积木那样把add方法搭出来了。
(define (add a b) (lambda (f) (lambda (x) ((b f) ((a f) x)))))

(add one two)
(lambda (f) (lambda (x) ((two f) ((one f) x)))
(lambda (f) (lambda (x) ((f (f ((one f) x))))))
(lambda (f) (lambda (x) (((f (f (f x)))))))

2.9
(define x (make-interval 6.12 6.8))
(define y (make-interval 4.47 4.9))
(newline)
(display (= (width-interval (add-interval x y)) (+ (width-interval x) (width-interval y))))
很遗憾，上面这段程序执行的结果是：#f
我很不解，用display分别打印了这两个结果，显示的都是0.555，于是我就更不解了。
郁闷了一小会儿，想起来自己默认是用的guile，于是改用MIT Scheme，还是#f。
但是MIT Scheme分别打印出来的两种方式的运算结果是：
    ;Loading "2.7.scm"...
    #f
    .5549999999999997
    .5550000000000002
    ;... done
这就清楚了，原来他们真的“有点”不一样。

2.13
数学上比较简单。
假设第一个区间的中点是v1，误差是t1；第二个区间的中点是v2，误差是t2。v1 t1 v2 t2都大于零。
乘积的区间是[v1*v2*(1-t1-t2-t1*t2), v1*v2(1+t1+t2+t1*t2)]，显然误差就是(t1+t2)/(1+t1*t2)
由于t1和t2都非常小，t1*t2就成芝麻了，忽略，结果就成了一个非常简单的t1+t2。
对于v1 t1 v2 t2的值分布的其他情况同理可证。

2.14
确实不一样，为什么呢？

2.15
要解释2.14的问题，需要回过头来看练习2.9。
2.9表明了两个区间进行加减的时候，结果区间的误差也是参数区间用同样运算符进行运算得到的结果。
区间相加，误差也相加
但是这个结论对于其他运算（减法、乘法和除法）竟然都并不成立。
对于减法，区间相减，误差还是相加。
沿用2.13的变量，两个区间相乘的结果的误差t=(t1+t2)/(1+t1*t2)。算出除法的结果误差有点麻烦，但结果也是t=(t1+t2)/(1+t1*t2)。
因此，对于par1和par2，需要对每一步的运算的误差进行计算，才能得到t(par1)和t(par2)。（好消息是t(one)=0）
步骤省略，结果是：
t(par1)=(t1+t2)(2+t1*t2)/(1+3*t1*t2+t1^2+t2^2) ~ 2*(t1+t2)
t(par2)=(t1+t2)
显然，按照这种计算方法，t(par2)只有t(par1)的一半不到。

2.16
为什么等价的代数表达式可能导致不同计算结果？
这本来就是一个伪命题。既然他们是等价的，计算结果就不应该不同。
唯一的可能就是，我们使用的方法不正确，也就是说，误差的计算是不能传递的。
要证明这一点很容易，很显然，除法就是误差传递的障碍。
没有缺陷的区间算术表示方法也许存在，但至少我不知道，嘿嘿。

关于区间运算，其实还有很多有意思的东西。下面这个链接就是一个入口，等我重新温习《具体数学》的时候再回头看吧：
http://wiki.drewhess.com/wiki/SICP_exercise_2.16

2.19
coin-values的排列顺序和最后结果无关，组合部分先后顺序。

2.22
(cons 4 ())和(list 4)等价，因为表的特征就是最后一个cons的后半部分指向nil
但是(cons () 4)产生的并不是(4)，而是(() . 4)。
为什么？这个序对的后半部分不是指向nil，当然和(list 4)完全不同。

2.23
如果想在一个条件分支中写多个语句，记得用cond

2.24
(define x (list 1 (list 2 3))) -> (1 (2 3)) -> (cdr x) = ((2 3))
(define y (cons 1 (list 2 3))) -> (1 2 3)   -> (cdr y) = (2 3)
(define z (cons 1 (cons 2 3))) -> (1 2 . 3) -> (cdr z) = (2 . 3)
为什么会有这样的不同呢？最关键的地方在于(list 1 2)和(cons 1 2)是不等价的。
(list 1 2)等价于(cons 1 (cons 2 nil))，表(list)的最后一个元素总是空(nil)。
这样就比较好画方块图和树了。

2.26
把list转化为cons就好

2.29
程序我没有测试，因为书上没有给测试数据，而且测试数据构造也太麻烦了，就pass了。
至于d)，修改非常简单，把多余的car干掉就好

2.32
程序没错，去google了一下别人的填空，一样，但是不知道为什么scheme就是跑不出来，guile也报错 -_-

2.42
这个题真的难了我一下，不过也可能是我头天晚上去K歌的缘故
卡住我的主要是棋盘的表示方式，其实只需要把棋盘看作一个栈，把行号逐一压进去就好
不过safe?函数的k参数迷惑了我，让我以为需要把行号和列号作为一个序对压栈
后来回头google了一下，还真的有人用序对的方法作出了这个题
不过这样的话效率肯定是比不过只用整数的咯

2.43
Louis把嵌套映射的顺序改变后，程序变成了完全的深度优先搜索，没有剪枝的效果，程序要走完整个棋盘的所有组合，也就是8^8次方种可能性……
因此Louis的程序的复杂度很显然是O(n^n)，因为queen-cols函数被他执行了n^n遍
相比之下2.42的程序的复杂度是O(n)，度量的准绳就是queen-cols函数被调用的次数
O(n^n)/O(n)并不能改变O(n^n)的本质，Louis的程序比老师的慢了O(n^n)个数量级

2.44
比较可惜，没法测试这个程序

2.49
鬼知道wave是由什么坐标连起来的……