sicp习题1.35和1.36解答

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

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

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

<!---->(fixed-point (lambda (x) (+ x (/ 1 x))) 1.0)

习题1.36解答：
首先修改fixed-point过程，使它输出每次猜测的近似值：

<!---->(define tolerance 0.00001)
(define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance))
(define (try f guess)
  (newline)
  (display guess)
  (let ((next (f guess)))
     (if (close-enough? guess next)
        next
        (try f next))))
(define (fixed-point f first-guess)
    (try f first-guess))

使用了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(在不同机器上可能结果不同，可平均阻尼一定快于不用平均阻尼）。

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

dennis 2007-05-15 18:44 发表评论