問題
英国の通貨はポンドとペニーから成り、コインには以下のバリエーションがある。
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
£2 = 200pをこれらのコインで用意するには、例えば以下の組み合わせがある。
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
このように、£2をこれらのコインで用意する場合の数を求めよ。
回答
1pのコインで、つじつまを合わせることにし、200未満を1p以外のコインで用意する場合の数を数える。
ukcoins = [2,5,10,20,50,100,200] -- 1のコインは200に到達しない部分を埋めるのに使うのでここには列挙しない。
-- 合計total以下のコインの組み合わせの場合の数を数える。
count _ [] = 1
count total (c:cs) = sum [count (total-m*c) cs |m<-[0..(total `div` c)]]
main = do
print $ count 200 ukcoins
感想
再帰的に数える方法を考える時間のほうがはるかに長かった。（受験生だったころならきっと一瞬で思いついたんでしょうね。）
思いつけばプログラムは非常に簡単。