分割数を求める．

lisp

ようやく積読状態にあった数学ガールを読んでいる．これはすごい．テスト前に覚えて2時間後には忘却の彼方だったテイラー展開や絶対不等式からの相加相乗平均の証明など，秀逸なものばかり．これは高校生の頃に読みたかった！


実は部分的に理解していないものもあるけれどとりあえず読みすすめると，分割数という章があって，気になる問題があった．


それまで，問題が出てもイメージだけして，あとは物語の主人公に説いてもらっていたのだが，問題を見てこれはちょっと解いてみよう．プログラムで．という気分になった．

額面が1円，2円，3円, 4円, ...となっているコインがあるとする．合計n円支払うためにコインの組み合わせは何通りあるか？この組み合わせの個数をP_nとする．P_nをnの分割数と呼ぶ．
たとえば3円を支払う方法には「3円が1枚」「2円が1枚と1円が1枚」，「1円が3枚」という3通りがある．

問題10-1
P_9を求めよ．

問題10-2
P_15 < 1000は成り立つか．


具体的な数でイメージをつくる．

1 => (1)
...
3 => (3) (2 1) (1 1 1)
4 => (4) (3 1) (2 2) (2 1 1) (1 1 1 1)
5 => (5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1)

なるほど．nが与えられたとき，kをnから1まで減らして（逆でもよい），n-kに関する分割数を足し合わせればよい．ただ，このままでは重複して数えてしまうので，n-kの分割数を数えるときは，k以下の数で分割するという制約を設ける．実は，n-k > kの場合はn-k以下である必要があるのだが．


数学が出来ないので，綺麗に数式化することができない．
ただ解法のアルゴリズムのイメージはついたので，後はコードに落とし込むだけ．


綺麗じゃないから説得力ないけれど，こういう問題はLispで書きやすい．

(defun bunkatu (n)
  (bunkatu-sub n n))

(defun bunkatu-sub (n m)
  (cond ((<= n 1) 1)
        (t
	 (let ((k (min n m)) (sum 0))
	   (loop
	     (cond ((zerop k) (return sum)))
	     (setq sum (+ sum
	                  (bunkatu-sub (- n k) k)))
	     (setq k (1- k)))))))

; 実行結果
(bunkatu 1) ; => 1
(bunkatu 2) ; => 2
(bunkatu 3) ; => 3
(bunkatu 4) ; => 5
(bunkatu 5) ; => 7
(bunkatu 9) ; => 30
(bunkatu 15); => 176

やったぁ，答えが出たー！証明はできないけれど，答えは得ることができました．


ごちゃごちゃしているけれど，メイン部分はシンプル．C系コードだとこんな感じ．

for(int k = n; k > 0; k--){
  sum += bunkatu-sub(n - k, k);
}

bunkatu-subは，用いる数をk以下という制約のもとで，分割数を求める関数．


というわけで数学ガールの続きを読みます．