SICP問題1.12

Pascal三角形の要素を計算する手続き

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

上から n 段, 左から k 番目の要素を計算する感じで。
※ 1段目の要素数は1, 2段目の要素数は 2, 3段目の要素数は3,...
k = 1, k = n の場合 要素は1
f(n, k) = f(n - 1, k - 1) + f(n - 1, k)
f(n, k) で (k <= 1) または (n <= k) の場合は 0

(define (pascal-triangle n k)
  (if (or (<= k 1) (<= n k))
      1
      (+ (pascal-triangle (- n 1) (- k 1))
         (pascal-triangle (- n 1) k)))
)

プログラマの数学

を読むと、 nCk (Cは組み合わせ, n=0スタート)ということなので次のようにも書けるかな。(0段目スタートで、要素0からスタートで数える)

(define (fact n) ; 階乗
   (if (= n 0)
       1
       (* n (fact (- n 1))))
)
(define (P n k) ; 順列
  (if (<= n k)
      (fact n)
      (/ (fact n) (fact (- n k))))
)
; これが pascal-triangleと同じになる
(define (C n k) ; 組み合わせ
  (/ (P n k) (P k k)))