イギリスの通貨はポンドとペンスから成り立っており、 1,2,5,10,20,50,100,200ペンスの8種類の硬貨が一般に流通している。
以下のような組み合わせで200ペンスを作ることができる。 1×100+1×50+2×20+1×5+1×2+3×1
200ペンスを払うには何通りの硬貨の組み合わせ方があるかを求めよ
硬貨を大きい方から考えて再帰的に考えて、その硬貨を使うことが可能な全て の枚数について残りの硬貨の組み合わせを考えて行けばよい。硬貨の種類を大 きいほうから順にあらわしたリストをcoinsとし、ある金額を与えられた硬貨の リストで何通りにあらわせるかを再帰的に求める関数をwaysとする。ここで硬 貨が1種類しかないときは、1ペンス硬貨ということがわかっているので1通りと する。硬貨が複数種類あるときは先頭の硬貨を0枚から与えられた金額を超えな い枚数まで使った全ての場合についてmapで残りの金額を残りの硬貨であらわし た場合の組み合わせを求め、その和を返す。
euler031 = ways 200 coins
where coins = [200, 100, 50, 20, 10, 5, 2, 1]
ways n (c:[]) = 1
ways n (c:cs) = sum $ map (\x -> ways (n - c * x) cs) [0..div n c]