乐正

Actions speak louder than words.

Sicp-ex1-12

问题

下面数值模式称为帕斯卡三角形: $$ \begin{array}{ccccccccccc} & & & & & 1 & & & & & \cr & & & & 1 & & 1 & & & & \cr & & & 1 & & 2 & & 1 & & & \cr & & 1 & & 3 & & 3 & & 1 & & \cr & 1 & & 4 & & 6 & & 4 & & 1 & \cr 1 & & 5 & & 10 & & 10 & & 5 & & 1 \cr \end{array} $$ 三角形边界上的数都是1,内部的每个数是位于它上面的两个数之和。请写一个过程,它采 用递归计算过程计算出帕斯卡三角形。

解答

1
2
3
4
5
(define (pascal row col)
  (if (or (= col 1) (= row col))
      1
      (+ (pascal (- row 1) (- col 1))
         (pascal (- row 1) col))))

测试

1
2
3
4
5
6
7
8
(pascal 3 2)
;Value: 2

(pascal 4 2)
;Value: 3

(pascal 5 3)
;Value: 6

拓展

有一个常用的计算帕斯卡三角的公式为(参考维基):

$$ C(n,k) = C{^n_k} = _nC_k = \begin{pmatrix} n \\ k \\ \end{pmatrix} = \frac {n!} {k!(n-k)!} $$

由此,可以得到计算帕斯卡三角的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
; 计算阶乘
(define (factorial n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* product counter)
                   (+ counter 1)
                   max-count)))
  (fact-iter 1 1 n))

; Pascal triangle
(define (pascal row col)
  (/ (factorial (- row 1))
     (* (factorial (- col 1))
        (factorial (- row col)))))

测试一下新版过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(pascal 4 2)
;Value: 3

(pascal 4 3)
;Value: 3

(pascal 4 4)
;Value: 1

(pascal 5 2)
;Value: 4

(pascal 5 3)
;Value: 6

新的过程是迭代计算过程,是线性复杂度的算法,比递归计算过程快了许多,而且没有了 递归深度的限制,可以计算很大的Pascal三角数:

1
2
(pascal 1024 36)
;Value: 119105169448695658119331865425553953128013711784936317985421906015

draft

« sicp-ex1-11 sicp-ex1-13 »

Comments