のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 31

英国の通貨(1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p) :pはペンス)を使って£2 (200p)を両替する方法は何通りあるか

いわゆる両替問題である。普通に漸化式をhaskellに書き下しても解けることは解ける。例えば100円を50円玉、10円玉、5円玉、1円玉に両替する場合の数は、50円玉を1つ除いた残りの50円を50円玉、10円玉、5円玉、1円玉で両替する場合の数と、100円を50円玉以外の貨幣で両替する場合の数の合計となるので、そのように関数を書けば良い。

が、明らかに無駄な重複があるので、ここでもData.Mapを使って効率化を図る。Data.Mapは以前problem14 で登場した。

mitstream.hatenablog.jp

今回もやっていることはほぼ同様。前に出てきた計算結果は表を参照することで計算を省略する。

実はほぼそのままの問題がここの記事に紹介されている。なので以下のコードはパクリやんけと言われればその通りである。大いに参考にさせていただいた。だって自力でやるには難しすぎたから。

自力では難しい★