Warning
这道练习的翻译有误,原文是『...Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.』,译文只翻译了『。。。它采用递归计算过程计算出帕斯卡三角形。』,这里应该是『帕斯卡三角形的各个元素』才对。
使用示例图可以更直观地看出帕斯卡三角形的各个元素之间的关系:
row:
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 . . . . . .
col: 0 1 2 3 4
如果使用 pascal(row, col)
代表第 row
行和第 col
列上的元素的值,可以得出一些性质:
pascal(row, col)
由 pascal(row-1, col-1)
(左上边的元素)和 pascal(row-1, col)
(右上边的元素)组成col
等于 0
(最左边元素),或者 row
等于 col
(最右边元素)时, pascal(row, col)
等于 1
比如说,当 row = 3
, col = 1
时, pascal(row,col)
的值为 3
,而这个值又是根据 pascal(3-1, 1-1) = 1
和 pascal(3-1, 1) = 2
计算出来的。
综合以上的两个性质,就可以写出递归版本的 pascal
函数了:
;;; 12-rec-pascal.scm
(define (pascal row col)
(cond ((> col row)
(error "unvalid col value"))
((or (= col 0) (= row col))
1)
(else (+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
测试一下这个 pascal
函数:
1 ]=> (load "12-rec-pascal.scm")
;Loading "12-rec-pascal.scm"... done
;Value: pascal
1 ]=> (pascal 4 0)
;Value: 1
1 ]=> (pascal 4 4)
;Value: 1
1 ]=> (pascal 4 2)
;Value: 6
前面给出的递归版本 pascal
函数的效率并不好,首先,因为它使用的是递归计算方式,所以它的递归深度受限于解释器所允许的最大递归深度。
其次,递归版本 pascal
函数计算值根据的是公式 \({row \choose col} = {row-1 \choose col-1} + {row-1 \choose col}\) ,这个公式带有重复计算,并且复杂度也很高,因此,前面给出的 pascal
函数只能用于 row
和 col
都非常小的情况。
要改进这一状况,可以使用帕斯卡三角形的另一个公式来计算帕斯卡三角形的元素:\({row \choose col} = \frac{row!}{col! \cdot (row-col)!}\) ,其中 \(row!\) 表示 \(row\) 的阶乘(factorial)。
阶乘可以利用书本 22 页的 factorial
函数(迭代版)来计算:
;;; p22-iter-factorial.scm
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
然后,使用 factorial
和给定的公式,给出迭代版本的 pascal
定义:
;;; 12-iter-pascal.scm
(load "p22-iter-factorial.scm")
(define (pascal row col)
(/ (factorial row)
(* (factorial col)
(factorial (- row col)))))
迭代版的 pascal
函数消除了递归版 pascal
的重复计算,并且它是一个线性复杂度的算法,因此,迭代版的 pascal
比起递归版的 pascal
要快不少,并且计算的值的大小不受递归栈深度的控制:
1 ]=> (load "12-iter-pascal.scm")
;Loading "12-iter-pascal.scm"...
; Loading "p22-iter-factorial.scm"... done
;... done
;Value: pascal
1 ]=> (pascal 4 0)
;Value: 1
1 ]=> (pascal 4 4)
;Value: 1
1 ]=> (pascal 4 2)
;Value: 6
1 ]=> (pascal 1024 256)
;Value: 346269144346889986395924831854035885865562696970381965629886488418277363006094610102022787857042680079787023567910689787903778413121916299434613646920250770005333708478791829291433521372230388837458830111329620101516314992938333258379799593534242588
最后一个测试尝试了对 (pascal 1024 256)
进行求值,计算结果是一个蛮大的数,如果使用递归版的 pascal
函数的话,这种计算就要非常非常久了,但是迭代版本还是可以很快地算出来。
See also
有很多不同的方式可以计算帕斯卡三角形的各个元素,可以参考维基百科的 Pascal’s triangle 页面、 Binomial coefficient 页面,或者任何一本组合数学方面的书籍。