Решение упражнения 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/фи, как написано в задании.

Comment from Spok
Date: November 26, 2013, 1:17 pm

Мне кажется у Вас определение процедуры cont-frac которая вызывала бы итеративный процесс слишком громоздко и избыточно. Думаю ткое определение ничем не хуже и легче в записи и понимании:

(define (cont-fract n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1.0) (/ (n i) (+ (d i) result)))))
  (iter k 0))

Да, согласен, такая процедура выполнится в среднем на один раз больше, чем Ваша, для вычисления нужного результата. Но мы не будем “плодить сущности” вводя let и кучу лишних локальных переменных в определение.

Comment from Ruslan Rokker
Date: January 17, 2014, 2:28 pm

Мои решения мне кажутся более элегантными 🙂

(define (cont-frac n d k)
  (if (= k 0)
      0
      (/ (n k) (+ (d k) (cont-frac n d (- k 1))))))

; b.
(define (cont-frac n d k)
  (cont-frac-iter n d k 0))

(define (cont-frac-iter n d k init)
  (if (= k 0)
      init
      (cont-frac-iter n d (- k 1) (/ (n k) (+ (d k) init)))

Comment from Irv
Date: January 10, 2016, 1:14 am

12 итераций

(define (cont-fract-iterative n d k)
  (define (iter i x)
    (if (> i 0)
        (iter (- i 1) (/ (n i) (+ (d i) x)))
        x))
  (iter k 0))

(define (cont-fract-recursive n d k)
  (if (= k 1)
      (/ (n 1) (d 1))  
      (/ (n (- k 1)) (+ (d (- k 1)) (cont-fract-recursive n d (- k 1))))))
     
(define (n i) 1.0)
(define (d i) 1.0)

(display 1.6180327868852458)
(newline)
(display (/ 1 (cont-fract-iterative n d 12)))
(newline)
(display (/ 1 (cont-fract-recursive n d 11)))

Comment from Kirill
Date: February 11, 2018, 8:58 pm

Получилось 12.

(define (cont-frac-test n d golden-ratio tolerance lim)
(define (cont i result)
(if (or (< (abs (- result golden-ratio)) tolerance)(= i 0)) (- lim i)
(cont (- i 1) (/ (n i) (+ (d i) result)))))
(cont lim 0))

(cont-frac-test
(lambda (i) 1.0)
(lambda (i) 1.0)
0.618033 0.00001 100)

Write a comment