Есть ли более эффективный способ написать этот рекурсивный процесс?
Меня попросили написать процедуру, которая вычисляет элементы треугольника Паскаля с помощью рекурсивного процесса. Я могу создать процедуру, которая возвращает одну строку в треугольнике или число в определенной строке.
Вот мое решение:
(define (f n)
(cond ((= n 1) '(1))
(else
(define (func i n l)
(if (> i n)
l
(func (+ i 1) n (cons (+ (convert (find (- i 1) (f (- n 1))))
(convert (find i (f (- n 1)))))
l))))
(func 1 n '()))))
(define (find n l)
(define (find i n a)
(if (or (null? a) (<= n 0))
'()
(if (>= i n)
(car a)
(find (+ i 1) n (cdr a)))))
(find 1 n l))
(define (convert l)
(if (null? l)
0
(+ l 0)))
Кажется, это работает нормально, но становится действительно неэффективно находить элементы большего ряда, начиная с (f 8)
, Есть ли лучшая процедура, которая решает эту проблему с помощью рекурсивного процесса?
Кроме того, как бы я написал это, если я хочу использовать итеративный процесс (хвостовая рекурсия)?
2 ответа
Существует несколько способов оптимизации алгоритма, и одним из лучших будет использование динамического программирования для эффективного расчета каждого значения. Вот мое собственное решение аналогичной проблемы, которое включает ссылки, чтобы лучше понять этот подход - это рекурсивный итеративный процесс. Ключевым моментом является то, что он использует операции мутации для обновления вектора предварительно вычисленных значений, и очень просто адаптировать реализацию для печати списка для данной строки:
(define (f n)
(let ([table (make-vector n 1)])
(let outer ([i 1])
(when (< i n)
(let inner ([j 1] [previous 1])
(when (< j i)
(let ([current (vector-ref table j)])
(vector-set! table j (+ current previous))
(inner (add1 j) current))))
(outer (add1 i))))
(vector->list table)))
В качестве альтернативы, заимствуя из решения @Sylwester, мы можем написать чисто функциональную хвостовую рекурсивную итерационную версию, которая использует списки для хранения предварительно вычисленных значений; в моих тестах это медленнее, чем в предыдущей версии:
(define (f n)
(define (aux tr tc prev acc)
(cond ((> tr n) '())
((and (= tc 1) (= tr n))
prev)
((= tc tr)
(aux (add1 tr) 1 (cons 1 acc) '(1)))
(else
(aux tr
(add1 tc)
(cdr prev)
(cons (+ (car prev) (cadr prev)) acc)))))
(if (= n 1)
'(1)
(aux 2 1 '(1 1) '(1))))
В любом случае это работает как ожидается для больших входов, это будет быстро для n
значения порядка пары тысяч:
(f 10)
=> '(1 9 36 84 126 126 84 36 9 1)
Уже представлено несколько решений, и они указывают на то, что использование динамического программирования является хорошим вариантом здесь. Я думаю, что это можно написать немного проще, хотя. Вот что я бы сделал как простое решение на основе списка. Это основано на наблюдении, что если строка n - (abcde), то строка n+1 - (a (+ ab) (+ bc) (+ cd) (+ de) e). Легко вычислить, что нужно перебрать хвосты (0 a b c d e) сбора ((+ 0 a) (+ a b) ... (+ d e) e).
(define (pascal n)
(let pascal ((n n) (row '(1)))
(if (= n 0) row
(pascal (- n 1)
(maplist (lambda (tail)
(if (null? (cdr tail)) 1
(+ (car tail)
(cadr tail))))
(cons 0 row))))))
(pascal 0) ;=> (1)
(pascal 1) ;=> (1 1)
(pascal 2) ;=> (1 2 1)
(pascal 3) ;=> (1 3 3 1)
(pascal 4) ;=> (1 4 6 4 1)
Это позволило использовать вспомогательную функцию maplist:
(define (maplist function list)
(if (null? list) list
(cons (function list)
(maplist function (cdr list)))))
(maplist reverse '(1 2 3))
;=> ((3 2 1) (3 2) (3))