Как итеративную и рекурсивную Ф(Х)


Определена функция f является по правилу, что F(н) = н, если н < 3 и Ф(н) = ф(Н-1) + 2Ф(н-2) + 3Ф(н-3), Если н>=3. Написать рекурсивную и итерационный процесс для вычисления F(Н).

Я написал следующее:

(define (f_r n)
  ; recursive
  (cond ((< n 3) n)
        (else (+ (f_r (- n 1)) 
                 (* 2 (f_r (- n 2))) 
                 (* 3 (f_r (- n 3)))))))

(define (f_i n)
  ;iterative
  (f_i-prime 1 0 0 n))

(define (f_i-prime n n-1 n-2 count)
  (cond ((= count 0) n)
        ((f_i-prime (+ n n-1 n-2) 
                    (+ n n-1) 
                    n-1 
                    (- count 1)))))

Что вы думаете?

Редактировать 1: С мое первое итерационное решение было ошибочным, вот исправленная версия:

(define (f_i n)
  ;iterative
  (f_i-prime 2 1 0 n))

(define (f_i-prime f_x+2 f_x+1 f_x n-x)
  (cond ((= n-x 0) f_x)
        ((f_i-prime (+ f_x+2 (* 2 f_x+1) (* 3 f_x) )
                    f_x+2 
                    f_x+1 
                    (- n-x 1)))))


738
1
задан 25 марта 2011 в 01:03 Источник Поделиться
Комментарии
1 ответ

Ваш итерационный определению не будет производить правильные результаты для большинства значений n.

При переписывании чисто рекурсивная функция как итеративный, один должен держать столько аккумуляторов, бывают случаи, основания. В итерационном шаге вычисления следующего значения, храните его в первом аккумулятора, поверните значения всех остальных аккумуляторов и декремент переменной цикла.

Вот реализация в вашем стиле:

(define (f_i n)
;iterative
;initial values of accumulators are f(2) = 2, f(1) = 1 and f(0) = 0; loop variable is n.
(f_i-prime 2 1 0 n))

(define (f_i-prime f-x+2 f-x+1 f-x n-x)
(cond ((= n-x 0) f-x) ; if n-x = 0, then n = x, so return f(x) = f(n).
((f_i-prime (+ f-x+2 (* 2 f-x+1) (* 3 f-x)) ; iterative step -- compute next value of f(x + 2);
f-x+2 ; ... rotate all other accumulators;
f-x+1
(- n-x 1))))) ; ... and decrement loop variable.

Можно включить вспомогательную функцию внутри функции main, используя мы рассматриваем letrec следующим образом (эта версия немного отличается от предыдущей в том, что переменная цикла отсчетов от 0 до n):

(define (f-iterative n)
(letrec
((f-aux
(lambda (x f-x+2 f-x+1 f-x)
(cond
((= x n) f-x)
((f-aux (+ x 1) (+ f-x+2 (* 2 f-x+1) (* 3 f-x)) f-x+2 f-x+1))))))
(f-aux 0 2 1 0)))

Можно также использовать сделать выражение, чтобы написать итеративную версию следующим образом:

(define (f-iterative n)
(do
((x 0 (+ x 1))
(f-x+2 2 (+ f-x+2 (* 2 f-x+1) (* 3 f-x)))
(f-x+1 1 f-x+2)
(f-x 0 f-x+1))
((= x n) f-x)))

Как на ваш рекурсивного определения, вы, возможно, пожелает мемоизации результатов для того, чтобы уменьшить сложность алгоритма, который в настоящее время за O(3 ^ N) времени. Мемоизация будет улучшить, что для линейной сложности.

3
ответ дан 25 марта 2011 в 09:03 Источник Поделиться