4

我被要求编写一个通过递归过程计算帕斯卡三角形元素的程序。我可以创建一个返回三角形中的单行或特定行中的数字的过程。

这是我的解决方案：

(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). 有没有更好的程序通过递归过程来解决这个问题？

另外，如果我想使用迭代过程（尾递归），我将如何编写它？

4

2 回答 2

3

有几种优化算法的方法，最好的方法之一是使用动态规划来有效地计算每个值。这是我自己对类似问题的解决方案，其中包括更好地理解这种方法的参考 - 这是一个尾递归的迭代过程。关键是它使用变异操作来更新预计算值的向量，并且调整实现以打印给定行的列表是一件简单的事情：

(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)
于 2014-09-29T15:58:27.750 回答
1

已经提出了许多解决方案，他们确实指出使用动态规划是一个不错的选择。我认为这可以写得更简单一些。这是我作为一个简单的基于列表的解决方案要做的事情。它基于以下观察：如果第 n 行是 (abcde)，则第 n+1 行是 (a (+ ab) (+ bc) (+ cd) (+ de) e)。一个易于计算的方法是迭代 (0 abcde) 收集 ((+ 0 a) (+ ab) ... (+ de) 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))
于 2014-09-30T01:24:27.730 回答