パスカルの三角形

scheme

コメント欄にてあいさんより質問を頂いたので挑戦してみました。

あい 『ちょっと質問なんですが、
パスカルの三角形で、

                                                            • -

m 0 1 2 3 4 ・・・
n
0 1
1 1 1
2 1 2
3 1 3 3 1
4 1 4 6 4 1
・
・
・

                                                            • -

P(n,m)を求める関数を作るとき
schemeでどう書いたらいいですか？
例えば
(P 4 2)
=6
みたいになるプログラムを作りたいんです。

From: http://d.hatena.ne.jp/walf443/20060512/1147448853#c1148982927

どうやったら良いか思いつかないのでid:hyukiさんのコード
http://sicp.g.hatena.ne.jp/hyuki/20060512/pascal
を参考にしてみる。

combinationとlineの定義はそのまま使えそう。。。

まずはｎ個までパスカルの三角形を求める関数を作成します。

(define (pascal n)
  (define (pascal-iter i n)
          (cond ((< i n)
                 (display (line i))
                 (newline)
                 (pascal-iter (+ i 1) n))))
  (pascal-iter 0 n))

(pascal 10)

(1)
(1 1)
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 10 10 5 1)
(1 6 15 20 15 6 1)
(1 7 21 35 35 21 7 1)
(1 8 28 56 70 56 28 8 1)
(1 9 36 84 126 126 84 36 9 1)

ここまでやってみてcombinationの定義を眺めていると、ようやくパスカルの三角形は2項係数で表せたことを思い出した。よく考えてみるとcombinationというのは組み合わせという意味だ。（ってそのまんま）

ということで、

(define (P n m)
  (cond ((= k 0) 1)
        ((= k n) 1)
        (else (+ (P (- n 1) k) (P (- n 1) (- k 1))))))

要するに _nC_k = \frac{n!}{k!(n-k)!}を定義すればよいようです。

階乗を定義してやるとより分かりやすく書けそう。

(define (combination n k)
  (define (factorial x) 
    (if (= x 0) 
        1       
        (* x (factorial (- x 1)))))
  (/ (factorial n) 
     (* (factorial k)
        (factorial (- n k)))))

反復を使っていないのでかなり直感的。

しかし _nC_k = \frac{n(n - 1)...(n - k)}{(n-k)!}なので、

(define (combination n k)
  (define (fact-iter init last)
    (if (= init last)
        last    
        (* init (fact-iter (+ init 1) last))))
  (/ (fact-iter k n)
     (fact-iter 1 (- n k))))

とも書ける。反復使っているし余計なものを約分してるのでこちらの方が効率よさそう。

とここまで書いてid:hyukiさんのコメント欄を見ると全く同じメッセージがっ！！もしかしてスパム？まぁ、いいや勉強になったし…。