RSS Feed

Posts Tagged ‘SICP’

  1. SICP练习题1.45——求n次方根

    December 19, 2011 by xudifsd

    SICP》第一章最后有个练习非常有意思:求n次方根。书的第一章几乎用了所有的篇幅来讲一些算法和抽象,并且在第一章第一节就说到了用牛顿迭代法来求一个数的平方根,在第一章最后一节的练习中要求一个数的n次方根。

    根据书上前面几节的说法,求x的平方根就是求函数y->x/y的不动点,而不动点的求法就相当简单了,随便猜一个数带入函数,如果结果不好再将结果带入函数,最终函数总会得到不动点。但是如果直接这样求平方根会有一个问题:函数并不收敛(假设最开始猜y,那么带入函数会得到x/y,将结果再带入函数又得到y),补救办法就是使用一个叫average damp的方法(实在找不到中文的翻译,直译过来就是平均阻尼),average-damp可以直接用下面函数定义出来:

    (define (average-damp f)
        (lambda (x)
            (average x (f x))))

    这个函数的作用就是取函数返回值和函数参数的平均数,这样先对y->x/y这个函数取average damp,再对结果取不动点就能得到平方根了。我们也能用同样的方法取一个数的三次方根,只要将函数换为y->x/y2即可,但是对于四次方根无法得到结果,原因也是不收敛,而解决办法竟然是对原始函数取两次average damp。题目要求我们做实验得出为了取n次方根而必须取average damp次数的规律,这样我们可以定义下面的函数:

    (define (fixed-point f guess)
     (define (close-enough? a b)
      (< (abs (- a b)) 0.0001))
     (let ((guess-value (f guess)))
      (if (close-enough? guess guess-value)
       guess
       (fixed-point f guess-value))))
    
    (define (repeated f n)
     (define (iter f n result)
      (if (< n 1)
       result
       (iter f (- n 1) (lambda (x) (f (result x))))))
     (iter f n identity))
    
    (define (average-damp f)
     (lambda (x)
      (average x (f x))))
    
    (define (average a b)
     (/ (+ a b) 2))
    
    (define (square x)
     (* x x))
    
    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp 2)
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    其中fixed-point需要一个函数f,和一个最初的猜测数,返回满足要求的不动点;而repeated将带入的函数f迭代n次。
    实验结果如下:

    #;1> (nth-root 8 3)
    2.00003461276416
    #;2> (nth-root 128 7)
    1.9999526734277

    但是一到8次方根以上程序便会在两个数之间跳转,因此需要再将函数average damp一次,而函数到了16次方后又需要average damp一次。这样看基本上得出了规律:只需要将所求的根数取log2即可,但是scheme只提供了以自然对数为底的log函数,不过只需要定义下面的函数就可以求以2为底的log了:

    (define (log2 x)
     (/ (log x) (log 2)))

    这样我们就能够解决1.45的习题了:

    (define (nth-root x n)
     (fixed-point
      ((repeated average-damp (floor (log2 n)))
       (lambda (y) (/ x (expt y (- n 1)))))
      1))

    由于数学能力有限实在是无法证明为什么结果是这样,而且对于average damp这样一种方法维基百科上竟然没有!以前的数学实在学得不怎么样啊。不过《SICP》的习题做起来确实很有意思,还教你直接求tan、黄金分割数还有e的方法。