首先,递归过程 pascal
程序可以用更简单的方式表达(假设非负、有效输入)- 就像这样:
(define (pascal x y)
(if (or (zero? y) (= x y))
1
(+ (pascal (sub1 x) y)
(pascal (sub1 x) (sub1 y)))))
现在来回答这个问题。可以将递归过程的实现转换为使用尾递归的迭代过程版本。但是,它比看起来更加棘手,而要完全理解它,必须掌握动态规划的工作原理。有关此算法的详细说明,请参考Steven Skiena的The Algorithm Design Manual第2版第278页。
这种算法不适合Scheme中的惯用解决方案,因为它要求我们作为解决方案的一部分修改状态(在本例中,我们正在更新向量中的部分结果)。这是一个相当人为的解决方案,并且我优化了表格内存使用方式,因此每次只需要一个行 - 下面是代码:
(define (pascal x y)
(let ([table (make-vector (add1 x) 1)])
(let outer ([i 1])
(when (<= i x)
(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-ref table y)))
事实上,在这种情况下,编写一个直接的迭代循环、在途中改变变量会更加自然。在
Racket中,代码如下:
(define (pascal x y)
(define current null)
(define previous null)
(define table (make-vector (add1 x) 1))
(for ([i (in-range 1 (add1 x))])
(set! previous 1)
(for ([j (in-range 1 i)])
(set! current (vector-ref table j))
(vector-set! table j (+ (vector-ref table j) previous))
(set! previous current)))
(vector-ref table y))
我们可以打印结果并检查所有三个实现是否有效。再次在
Racket中:
(define (pascal-triangle n)
(for ([x (in-range 0 n)])
(for ([y (in-range 0 (add1 x))])
(printf "~a " (pascal x y)))
(newline)))
(pascal-triangle 5)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1