パスカルの三角形は数を三角形状に並べた物で、最上段に1があり、そこから下の行はその位置の右上の数と左上の数の和を記入して行ったものです。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1(x:3 Y:6)の値は(x:2 Y:5)と(x:3 Y:5)の和。(x:2 Y:5)の値は・・・と再帰で求められます。
1 2 3 4 5 6 X
+-------------------------
1 | 1
2 | 1 1
3 | 1 x 1
4 | 1 x x 1
5 | 1 x x x 1
6 | 1 x ● x x 1
Y
;; 位置 x y の値
(defun g-pascal (x y)
(if (or (= x 1) (= x y))
1
(+ (g-pascal (- x 1) (- y 1))
(g-pascal x (- y 1)))))
CL-USER> (trace g-pascal)
(G-PASCAL)
CL-USER> (g-pascal 3 6)
0: (G-PASCAL 3 6) ;; (x3 y6)は(x2 y5)と(x3 y5) の計
1: (G-PASCAL 2 5) ;; (x2 y5)は(x1 y4)と(x2 y4) の計
2: (G-PASCAL 1 4) ;; (x1 y4)の値は1
2: G-PASCAL returned 1
2: (G-PASCAL 2 4)
3: (G-PASCAL 1 3)
3: G-PASCAL returned 1
3: (G-PASCAL 2 3)
4: (G-PASCAL 1 2)
4: G-PASCAL returned 1
4: (G-PASCAL 2 2)
4: G-PASCAL returned 1
3: G-PASCAL returned 2
2: G-PASCAL returned 3
1: G-PASCAL returned 4
1: (G-PASCAL 3 5)
2: (G-PASCAL 2 4)
3: (G-PASCAL 1 3)
3: G-PASCAL returned 1
3: (G-PASCAL 2 3)
4: (G-PASCAL 1 2)
4: G-PASCAL returned 1
4: (G-PASCAL 2 2)
4: G-PASCAL returned 1
3: G-PASCAL returned 2
2: G-PASCAL returned 3
2: (G-PASCAL 3 4)
3: (G-PASCAL 2 3)
4: (G-PASCAL 1 2)
4: G-PASCAL returned 1
4: (G-PASCAL 2 2)
4: G-PASCAL returned 1
3: G-PASCAL returned 2
3: (G-PASCAL 3 3)
3: G-PASCAL returned 1
2: G-PASCAL returned 3
1: G-PASCAL returned 6
0: G-PASCAL returned 10
10
;; 位置 x y の値 (defun g-pascal (x y) (if (or (= x 1) (= x y)) 1 (+ (g-pascal (- x 1) (- y 1)) (g-pascal x (- y 1))))) ;;行 y の表示 (defun repeat (x y max outstr) (if (> x max) outstr (repeat (+ x 1) y max (format nil "~A~A " outstr (format nil "~4D" (g-pascal x y)))))) (defun ptable (y max) (unless (> y max) (progn (format t "~A ~%" (repeat 1 y y "")) (ptable (+ y 1) max)))) (ptable 1 15) ;; => 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 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
末尾再帰でリストを作ってみます。
;; x から max までのリストを作って返す。 ;; (mk-list 1 10) ;=> (1 2 3 4 5 6 7 8 9 10) (defun mk-list (x max) (if (= x max) (list max) (cons x (mk-list (+ x 1) max)))) ;; リストの x 番目の要素を取得 (defun get-cell (x ls count) (cond ((null ls) nil) ((= x count) (car ls)) (t (get-cell x (cdr ls) (+ count 1))))) ;; パスカルの三角形から x yを指定して要素を取得。 (defun read-pascal (ls x y) (get-cell x (get-cell y ls 1) 1)) ;; 新しいパスカルの三角形の要素を x yを指定して取得。 (defun pascal (ls x y) (if (or (<= x 1) (<= y 1) (>= x y)) 1 (+ (read-pascal ls (- x 1) (- y 1)) (read-pascal ls x (- y 1))))) ;; 1行を生成。 (defun pascal-line (ls n) (mapcar #'(lambda(x)(pascal ls x n)) (mk-list 1 n))) ;; パスカルの三角形を作成 (defun pascal-triangle (ls n cnt) (if (> n cnt) ls (pascal-triangle (append ls (list (pascal-line ls n))) (+ n 1) cnt))) (pascal-triangle '() 1 15) ;;=> ((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) (1 10 45 120 210 252 210 120 45 10 1) (1 11 55 165 330 462 462 330 165 55 11 1) (1 12 66 220 495 792 924 792 495 220 66 12 1) (1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1) (1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1)) ;; (見やすいように手作業で改行)
