расчета Итерационного дерева в схеме

Question

Я пытаюсь реализовать функцию, определенную как таковые:

f(n) = n if n < 4 
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) + 4f(n - 4) if n >= 4 

Итерационный способ сделать это было бы начать на дне, пока я не попал n, так что если п = 6 : попытка

f(4) = (3) + 2(2) + 3(1) + 4(0)  | 10 
f(5) = f(4) + 2(3) + 3(2) + 4(1) | 10 + 16 = 26 
f(6) = f(5) + 2f(4) + 3(3) + 4(2) | 26 + 2(10) + 17 = 63 

Реализация:

; m1...m4 | The results of the previous calculations (eg. f(n-1), f(n-2), etc.) 
; result | The result thus far 
; counter | The current iteration of the loop--starts at 4 and ends at n 
(define (fourf-iter n) 
    (cond [(< n 4) n] 
     [else 
     (define (helper m1 m2 m3 m4 result counter) 
      (cond [(= counter n) result] 
       [(helper result m1 m2 m3 (+ result m1 (* 2 m2) (* 3 m3) (* 4 m4)) (+ counter 1))])) 
     (helper 3 2 1 0 10 4)])) 

Несколько проблем:

• Возвращаемый результат один итерации меньше, чем это должно быть, потому что фактические расчеты не происходят не до рекурсивного вызова
• Вместо того, чтобы использовать определенный алгоритм для вычисления F (4), I «м просто положить его прямо там, что f(4) = 10
• в идеале я хочу начать result на 0 и counter на 3, так что расчеты применяются к m1 через m4 (и так, что f(4) фактически рассчитывается из вместо того, чтобы быть предварительно) , но затем 0 будет использоваться для m1 в следующей итерации п, когда оно должно быть результатом f(4) вместо (10)

TL; либо результат вычисления др задерживается, или сам результат задерживается. Как я могу написать это правильно?

Answer 1

Я думаю, что подходящий способ «Scheme-ish» написать функцию, определенную рекурсивно подобной, - использовать memoization. Если функция f равна memoized, то при вызове f(4) сначала она просматривает 4 в таблице значений ключа и, если она ее находит, возвращает сохраненное значение. В противном случае он просто вычисляет нормально, а затем сохраняет все, что он вычисляет в таблице. Поэтому f будет никогда не оценивать одинаковые вычисления дважды. Это аналогично шаблону создания массива размером n и заполнению значений, начиная с 0, создавая решение для n. Этот метод называется динамическим программированием, а memoization и динамическое программирование - действительно разные способы взглянуть на одну и ту же стратегию оптимизации - избегая одновременного вычисления одной и той же вещи. Вот простая функция memo Ракетка, которая принимает функцию и возвращает memoized версию этого:

(define (memo f) 
    (let ([table (make-hash)]) 
    (lambda args 
     (hash-ref! table 
       args 
       (thunk (apply f args)))))) 

Теперь мы можем написать функцию f рекурсивно без необходимости беспокоиться о проблемах производительности когда-либо вычисления тот же результат в два раза, Таким образом, происходит от экспоненциального алгоритма время вниз к линейной, сохраняя при этом реализация проста:

(define f 
    (memo 
    (lambda (n) 
     (if (< n 4) 
      n 
      (+ (f (- n 1)) 
      (* 2 (f (- n 2))) 
      (* 3 (f (- n 3))) 
      (* 4 (f (- n 4)))))))) 

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

---

Если вы хотите правильно хвост рекурсивного решения, ваш лучший подход, вероятно, использовать имени пусть конструкта. Если вы сделаете (let name ([id val] ...) body ...), то звонок (name val ...) в любом месте body ... вернется в начало let с новыми значениями val ... для привязок. Пример:

(define (display-n string n) 
    (let loop ([i 0]) 
    (when (< i n) 
     (display string) 
     (loop (add1 i))))) 

Используя это делает хвостовую рекурсию решение вашей проблемы гораздо менее многословным, чем определения вспомогательной функции и назвав его:

(define (f n) 
    (if (< n 4) 
     n 
     (let loop ([a 3] [b 2] [c 1] [d 0] [i 4]) 
     (if (<= i n) 
      (loop (fn+1 a b c d) a b c (add1 i)) 
      a)))) 

(define (fn+1 a b c d) 
    (+ a (* 2 b) (* 3 c) (* 4 d))) 

Эта версия функции отслеживает четырех значений для f, а затем использует их для вычисления следующего значения и перерезает самое старое значение. Это создает решение, сохраняя только четыре значения в памяти, и оно не хранит огромную таблицу, хранящуюся между вызовами. Вспомогательная функция fn+1 предназначена для объединения четырех предыдущих результатов функции в следующий результат, она доступна только для удобства чтения. Это может быть функция для использования, если вы хотите оптимизировать использование памяти. Однако использование memoized версии имеет два преимущества:

1. Мемуаризованная версия намного легче понять, рекурсивная логика сохраняется.
2. В memoized версия сохраняет результаты между вызовов, поэтому если вы звоните f(10) и затем f(4), второй вызов будет только таблица поиска в постоянная время, потому что вызов f(10) хранить все результаты для вызова f с n от 0 до 10 .