Решение упражнения 1.37 из SICP

24 October, 2007 (21:05) | Решения упражнений

Сначала реализуем процедуру cont-frac, порождающую рекурсивный процесс:

> (define (cont-frac n d k)
    (define (iter i)
      (/ (n i) (+ (d i)
                  (if (< i k)
                      (iter (+ i 1))
                      0))))
    (iter 1))
> (/ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100))
1.618033988749895

Найдем число итераций, необходимых для вычисления φ с точностью до четвертого знака с помощью cont-frac. Эталон вычислим с помощью метода поиска неподвижной точки из упражнения 1.35:

(define (fixed-point f first-guess tolerance)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
         (if (close-enough? guess next)
             next
             (try next))))
  (try first-guess))
(define golden-ratio (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0 0.000001))
(define (count-iterations function value tolerance)
  (define (try k)
    (define (close-enough? a b)
      (< (abs (- a b)) tolerance))
    (if (close-enough? (function k) value)
        k
        (try (+ k 1))))
  (try 1))
(define (golden-ratio-function k)
  (/ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)))
> (count-iterations golden-ratio-function golden-ratio 0.00001)
13

Как видим, достаточно 13 итераций.

Теперь запишем процедуру cont-frac так, чтобы порождаемый ей процесс был итеративным:

> (define (cont-frac n d k)
    (define (iter i accum)
      (let ((accum (/ (n i) (+ (d i) accum)))
            (i (- i 1)))
        (if (> i 0)
            (iter i accum)
            accum)))
    (iter k 0))
> (/ 1 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100))
1.618033988749895

Итеративный процесс фактически производит вычисления с “хвоста” цепной дроби и поднимается вверх к ее началу, аккумулируя значения.

Comments

Comment from Nergal
Date: October 18, 2009, 12:36 am

С моей точки зрения, ответ 11 итераций. На 11 итерации разница между эталоном и считаемым приближением порядка 0.00005, что уже даёт нам точность в 4 знака.

Comment from smersh
Date: January 9, 2010, 8:45 pm

У меня получилось 12, с таким вот кодом:

(define (cont-frac Ni Di k)
(define (proc count)
(/ (Ni count) (+ (Di count)
(if (= count k)
1
(proc (+ count 1))))))
(proc 1))

(define (fixed-point f first-guess tolerance)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try prev count)
(let ((next (f count)))
(if (close-enough? prev next)
count
(try next (+ count 1)))))
(try first-guess 1))

(define (c-f-c k)
(/ 1 (cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k)))

(fixed-point c-f-c 1 0.00005)
12

Comment from Dmitri
Date: July 27, 2010, 5:32 pm

В этой строке:
(define golden-ratio (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0 0.000001))
у вас ошибка. Лямбду следует определять как (lambda (x) (/ 1 (+ 1 x))) (т.е. поменять знаки сложения и деления).
В таком случае функция возвращает верный ответ: 0,618033989 (а не 1.6… как у вас) - именно это число равно 1/фи, как написано в задании.

Write a comment