庄周梦蝶

    本节内容介绍了将高阶过程用于一般性过程，举了两个例子：区间折半查找方程根和找出函数不动点。习题也是围绕这两个问题展开。今天工作上遇到了比较郁闷的事情，这周末确定要加班，心情实在糟糕!-_-，先做两题吧，有空再继续。

习题1.35，证明黄金分割率φ是变换x->x+1/x的不动点，并利用这个事实通过过程fixed-point计算出φ 值。

这道题目很简单了，根据黄金分割的定义，φ满足方程：φ的平方=φ+1；两边同除以φ，得到方程：
φ=φ+1/φ。根据函数不动点定义f(x)=x，可以得到φ就是变换x->x+1/x的不动点。利用fixed-point过程写出：

习题1.36解答：
首先修改fixed-point过程，使它输出每次猜测的近似值：
使用了newline和display基本过程，然后要求x->log(1000)/log(x)的不动点，并比较平均阻尼方式和非平均阻尼方式的计算步数。
首先，请看非平均阻尼方式(直接看截图了)，我们以2作为初始猜测值：

可以看到，非平均阻尼方式执行了33步才计算出了x值。

再看平均阻尼方式，方程x=log(1000)/log(x)可以转化为：
x=(1/2)(x+log(1000)/log(x))

看看结果：

仅仅执行了9步就完成了计算，大概是非平均阻尼方式的1/3(在不同机器上可能结果不同，可平均阻尼一定快于不用平均阻尼）。

由此可见：使用平均阻尼技术比不用平均阻尼技术收敛的快得多。

    此题与1.32、1.33是一个系列题，没什么难度，只不过把sum的加改成乘就可以了，递归与迭代版本相应修改即可：
   分号注释的是递归版本。利用product过程生成一个计算pi的过程，也是很简单，通过观察公式的规律即可得出：
测试一下:


再来看习题1.32，如果说sum和product过程是一定程度的抽象，将对累积项和下一项的处理抽象为过程作为参数提取出来，那么这个题目要求将累积的操作也作为参数提取出来，是更高层次的抽象，同样也难不倒我们：

OK,其中combiner是进行累积的操作，而null-value值基本值。现在改写sum和product过程，对于sum过程来说，累积的操作就是加法，而基本值当然是0了：

而对于product，累积操作是乘法，而基本值是1，因此：

测试一下过去写的那些测试程序，比如生成pi的过程，可以验证一切正常！

上面的accumulate过程是递归版本，对应的迭代版本也很容易改写了：

再看习题1.33，在accumulate的基础上多增加一个filter的参数（也是一个过程，用于判断项是否符合要求），在accumulate的基础上稍微修改下，在每次累积之前进行判断即可：


比如，求a到b中的所有素数之和的过程可以写为（利用以前写的prime?过程来判断素数):

测试一下：

    这节开始介绍将用高阶函数做抽象的技术，比如将过程作为参数、返回值等等。习题1.30要求将书中的sum递归过程改造为迭代版本，解答如下：

测试一下，比如求pi的过程：

(sum 1 10)：
=》 55

    再提下1.29的题目，使用辛普森规则计算定积分，一开始我没有使用sum过程，自己写了递归：

    复用sum过程，也可以这样写：

    这一题不是我独立想出来的咯,比较遗憾，没有认真读书中的注解，通过google解决的，一搜索才发现网上已经有很多的scip习题的解答，我这个倒是画蛇添足了!-_-。想一想还是有写下去的必要，尽管牛人多如牛毛，自己还是潜下心来一步一步向前。
   来自http://dev.csdn.net/develop/article/64/64485.shtm

; ======================================================================
;
;          Structure and Interpretation of Computer Programs
;                  (trial answer to excercises)
;
;                  计算机程序的构造和解释(习题试解)
;
;                                             created: code17 02/28/05
;                                             modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================

;; SICP No.1.25
;; 本题为理解题

;; 直接定义(expmod base exp m)为base^exp基于m的模(modulo)
;; (define (expmod base exp m)
;;   (remainder (fast-expt base exp) m))
;; 在理想情况下是正确的，在语义上与原定义是等价的，甚至递归层数
;; 都是一样的，而且更加直观。
;;
;; 但在实践中，这样的定义是不可行的，这也是为什么我们要采用原文中的定义
;; 的原因：因为base^exp很可能是一个非常大的数。比如，当我们取第二个
;; 测试例子中的n=1000000时，base是[1,999999]区间中的任意
;; 随机数，它的平均取值为50000，而exp=1000000。50000^1000000是一个大得
;; 惊人的数，无论是fast-expt的层层函数调用计算，还是用remainder对其取模，
;; 计算量都是很大的。
;;
;; 而相反，原始的expmod函数
;; (define (expmod base exp m)
;;   (cond ((= exp 0) 1)
;;         ((even? exp)
;;          (remainder (square (expmod base (/ exp 2) m))
;;                     m))
;;         (else
;;          (remainder (* base (expmod base (- exp 1) m))
;;                     m))))
;; 通过分解(a*b mod n) 为 ((a mod n) * (b mod n) mod n)，使得每层递归
;; 调用的计算参数和返回值总是小于n (x mod n < n)，即便是计算过程中出现
;; 的最大数(a mod n) * (b mod n) 也依然是要小于n^2, 相对于前者n^n的数
;; 量级，实在是小得多，这样就避免了大数的计算问题。
;;
;; 比如经测试，在使用新的expmod的情况下，1009的验证需要1.2ms的时间，
;; 1000003的验证需要 93680ms，远高于原来的expmod函数。
;;
;; 这也同时印证了我们在1.24题中的分析，同样的操作在不同字长的数字上的
;; 代价是不同的。1000000的验证时间现在是1000的8000多倍，远不再是2倍左右
;; 的关系。在1.24中的，因为expmod算法的控制，操作数最多是n^2级的，字长
;; 所引起的差距并不明显，只在10^6-10^12间产生了一点点阶跃；而这里的算法
;; 中, 操作数可以达到n^n级，当n=1000时，1000^1000的字长大约在10000位(二
;; 进制数)左右，而n=1000000时1000000^1000000的字长则达到在20000000位(二
;; 进制数)左右，这字长的巨大差距导致了我们在1.24中已经发现的问题更加明显。

    尽管两个过程在语义和原理是相通的，但因为在不同的场景中使用，所碰到的情况就截然不同了，算法在不同场景下的表现差异明显，还需仔细斟酌。

    这两道题目没什么难度了，幂运算是连续乘，乘法运算就是连续加，改造一下书中的例子和习题1.16就可以了，还是分析一下。

习题1.17:
已知两个过程,double过程可以求出一个整数的两倍，而halve过程将一个偶数除以2;要求写出一个过程，只用对数个步骤计算两个整数的乘积。

解答:
计算a*b，考虑两种情况：
1)当b是偶数时：
a*b=2(a*(b/2))
2)当b是奇数时：
a*b=a*(b-1)+a

通过递归直接得到lisp过程，很好理解了，预先定义了两个已知过程double和halve：

习题1.18:将1.17的递归过程改写为迭代过程，保持对数个步骤

分析：递归转化为迭代，关键是要抓住状态迁移间的不变量，我们给它一个状态变量c，问题归结为如何保持c+a*b不变。
1)当b是偶数：
c+a*b=c+(2a)*(b/2))
在此过程中的状态变换：

2)当b是奇数:
c+a*b=(c+a)+a*(b-1)
回溯此状态转换：

由此可以得到该过程的迭代版本，两个已知过程与上同：

    此题充分展示了如何将递归转化为迭代的技巧：定义一个不变量，要求它在迭代状态之间保持不变！题目如下：
写一个过程求平方，并且只用对数个步骤。

解答：
考虑一个附加状态a，如何保持ab**n(b**n表示b的n次方）在状态改变间保持不变.
1)当n是偶数：
a(b²)^n/2 = abⁿ
bⁿ = (b^n/2)² = (b²)^n/2
在这个过程中回溯状态的迁移：


2)当n是奇数：
(ab)b^(n-1) = abⁿ
回溯状态的变迁：

就此可以写出lisp过程了:

这道题目一开始我的解答完全错了！-_-，我理解错了题意，一直将指数对半折，这样的步骤是n/2步而不是对数步骤，阶仍然是(theta)(n)：

    本小节主要介绍了阶的概念，与算法中计算时间和空间复杂度类似。给了一个过程：
    这个过程用于求弧度的正弦值
a)在求值(sine 12.15)时，p过程将被使用多少次？
答：
(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))))))
显而易见，p被调用了5次

b)由过程sine所产生的计算过程使用的空间和步数增长的阶是多少？
从上面的分析可以看出，空间和步数的增长都跟p的调用次数成正比，也就是与递归次数是线性关系。
当|a|<0.1时，递归次数为0
当|a|>0.1时，递归的最大次数满足条件：|a|/3**num<0.1，这里的3**num采用ruby记法表示3的num次方，此时递归次数num<log3(10a)
因此，对于空间和步数的阶应该为:R(n)=(theta)lg(n)

    这个小节主要讲解了迭代与树形递归，递归比起迭代更易于理解和直观，而迭代相比于递归则效率更高，一般计算机的递归实现都是使用堆栈结构实现的，当递归层次太深的时候容易导致栈溢出，而迭代则没有这样的问题。
习题1.11是这样的：
    如果n<3，那么f(n)=n;如果n>=3，那么f(n)=f(n-1)+2f(n-2)+3f(n-3)，请写一个采用递归计算过程f的过程，再改写一个采用迭代计算过程计算f的过程。

解答：
1.采用递归的话就很简单了，可以将条件直接描述为一个lisp过程，没什么好解释的：
2。迭代就相对麻烦点，将递归转化为迭代，关键在于找出迭代每一步之间的差异，这个差异就是每次迭代变化的量，找出这个固定编号的量就是问题的关键。很容易就可以看出f(n)和f(n-1)之间的差距就是：2f(n-2)+3f(n-3)。这就提示我们需要保持3个顺序的状态变量：f(n-2)、 f(n-1) 、f(n)，迭代向前一步的时候：f(n-2)被f(n-1)取代，f(n-1)被f(n)取代，将f(n)+2f(n-2)+3f(n-3)做为新的f(n)。迭代是自底向上，初始化的3个变量就是0、1、2，这样就可以相应地写出一个迭代版本的解答：

可以测试一下，在n数目比较大的时候，递归版本速度明显变慢甚至栈溢出，而迭代版本就比较快了。

习题1.12：用递归过程描述帕斯卡三角（或者说杨辉三角）
根据杨辉三角的特点，x行y列的数字等于x-1行y列的数字和x-1行y-1列的数字之和，就可以解决这个问题：

    综合了习题1.6提出的误差过大问题，采用相对误差进行求值，题目是要求使用牛顿近似求立方根公式写出scheme过程：
测试一下：

    这是《计算机程序的构造与解释》中的一道习题，如何去判断一个scheme解释器是采用什么方式进行求值的？应用序 or 正则序。应用序是先对参数求值而后应用，而正则序则相反——完全展开而后归约求值。正则序相比于应用序，会部分存在重复求值的情况。习题是这样的：
    Ben Bitdiddle发明了一种检测方法，能够确定解释器究竟采用的哪种序求值，是采用正则序，还是采用应用序，他定义了下面两个过程：
  
    而后他求值下列的表达式：
   如果解释器采用的是应用序求值，ben将会看到什么情况？如果是正则序呢？

    分别分析下这两种情况下解释器的求值过程：
1.如果解释器是应用序，将先对过程test的参数求值，0仍然是0，(p)返回的仍然是(p)，并且将无穷递归下去直到栈溢出，显然，在这种情况下，解释器将进入假死状态没有输出。

2.如果解释器是正则序，完全展开test过程：
接下来再进行求值，显然0=0，结果将返回0。

    一般lisp的解释器都是采用应用序进行求值。这个问题在习题1.6中再次出现。我们知道scheme已经有一个cond else的特殊形式，为什么还需要一个if else的特殊形式呢？那么我们改写一个new-if看看：

写几个过程测试一下：
结果一切正常，但是，当这3个参数是过程的时候会发生什么情况呢？在这3个参数如果存在递归调用等情况下，解释器也将陷入无限循环导致栈溢出！比如书中的求平方根过程用new-if改写：

因为解释器是应用序求值，将对new-if过程的3个参数求值，其中第三个参数也是一个过程(sqrt_iter (improve guess x) x)) 递归调用自身，导致无限循环直到栈溢出。