Бесконечная непрерывная дробь - итерационные и рекурсивные


Даны следующие упражнения:

Упражнения 1.37. а. Бесконечное цепная дробь-это выражение форме

infinite continued fraction

Как пример, можно показать, что бесконечно продолжающееся расширение доли с NI и Ди все равно 1 производит 1/, где-золотое сечение (описано в разделе 1.2.2). Одним из способов для приблизительного бесконечное продолжение фракция для усечения расширения после определенного количества терминов. Такой усечение -- так называемый к-терм конечная непрерывная дробь имеет форма

k term finite continued fraction

Предположим, что N и D являются процедуры один аргумент (термин индекс I), что вернуть NI и Ди условий продолжение Часть. Определить процедура прод-ГРП, такие, что оценки (прод-ГРП N д к) вычисляет значение к-конечный срок непрерывной дробью. Проверить процедуры аппроксимации 1/ через

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

для последовательных значений K. Как большие вы должны принять к для того, чтобы получить приближение точностью до 4 после запятой?

б. Если ваш Конт-ГРП процедуры порождает рекурсивный процесс, пишите одна, что порождает итерационный процесс. Если она порождает итеративный процесс, напишу один, что создает рекурсивный процесс.

Я написал следующие две функции:

Рекурсивно:

(define (cont-frac n_i d_i k)
  (define (recurse n)
    (define (next n) (+ n 1))
    (if (= n k) (/ (n_i k) (d_i k)) 
        (/ (n_i n) (+ (d_i n) (recurse (next n))))))
  (recurse 1))

Итерационный:

(define (i-cont-frac n_i d_i k)
  (define (iterate result n)
    (define (next n) (- n 1))
    (if (= n 1) (/ (n_i n) result)
        (iterate (+ (d_i (next n))           
                    (/ (n_i n) result)) (next n))))
  (iterate (d_i k) k))

Что вы думаете о моем решении?



1538
0
задан 31 марта 2011 в 02:03 Источник Поделиться
Комментарии
2 ответа

Обратите внимание, что ваше определение непрерыв-фрак , а я-прод-ГРП принимают в качестве аргументов функции Н И Д, и не n_i или d_i (которые, думаю, будут конкретные значения Н И Д в индексе я). Я хотел избежать этой путаницы, назвав правильно аргументы.

Определение я-прод-ГРП могут быть улучшены путем переписывания базового варианта. Когда iterant равен нулю, то результат должен быть ноль, а также.

Можно также абстрактные идеи начальной и терминальной стоимости в iterant, и начальное значение результата. Вот реализация этих идей:

(define (cont-frac n d k)
(define initial-result 0)
(define initial-i 0)
(define terminal-i k)
(define (recurse i)
(if (= i terminal-i)
initial-result
(let
((next-i (+ i 1)))
(/ (n next-i) (+ (d next-i) (recurse next-i))))))
(recurse initial-i))

(define (i-cont-frac n d k)
(define initial-result 0)
(define initial-i k)
(define terminal-i 0)
(define (iterate result i)
(if (= i terminal-i)
result
(let
((next-i (- i 1)))
(iterate (/ (n i)
(+ (d i) result))
next-i))))
(iterate initial-result initial-i))

Обратите внимание на разницу в начально-я, терминала-я и далее-я значения этих определений. Это согласуется с тем, как рекурсия и итерация работы в этих функциях.

Обратите внимание, что рекурсивные определения необходимо использовать пусть для того, чтобы получить следующее значение я , чтобы разрешить для 1-индексированные характер функций Н И Д и вернуть правильное значение равное нулю, когда к нулю. Если мы предположим, что к - это не ноль, мы можем переписать упрощенная версия рекурсивного определения, например:

(define (cont-frac n d k)
(define initial-result 0)
(define initial-i 1)
(define terminal-i k)
(define (recurse i)
(define (next i) (+ i 1))
(/ (n i) (+ (d i) (if (= i terminal-i) initial-result (recurse (next i))))))
(recurse initial-i))

1
ответ дан 31 марта 2011 в 12:03 Источник Поделиться

Ваши решения выглядят хорошо.

Я не вижу существенно разные способ сделать рекурсивное решение. Мои предпочтения на пробелы (в основном, касающиеся если) немного отличаются. Кроме того, я не определяем функцию следующим в этой ситуации. Если по каким-то причинам вы не хотите просто поставить (+ Н 1) в качестве аргумента давайте выражение будет более применимо.

(define (cont-frac n_i d_i k)
(define (recurse n)
(if (= n k)
(/ (n_i k) (d_i k))
(/ (n_i n) (+ (d_i n) (recurse (+ n 1)))) ))
(recurse 1))

Или

(define (cont-frac n_i d_i k)
(define (recurse n)
(if (= n k)
(/ (n_i k) (d_i k))
(let ((next_n (+ n 1)))
(/ (n_i n) (+ (d_i n) (recurse next_n)))) ))
(recurse 1))

ПС - написать функцию для nth_odd_square и попробовать этот

(/ 4.0 (+ 1 (i-cont-frac nth_odd_square (lambda (i) 2.0) 500000)))

1
ответ дан 31 марта 2011 в 05:03 Источник Поделиться