補足盛り沢山。
この一問だけで色々な書き方を知ることができた。
この一問だけで色々な書き方を知ることができた。
補足1
この辺やこの辺を参考に。単位の大きい硬貨から順番にリストを回していくパターン。
これは euler31-1.hs の変形バージョンってところかな。
補足2
この辺を参考に。これは、大幅にやり方を変えたトリッキーな感じの解法。
1ペンスだけで2ポンドを作る組み合わせ
f1 nは一通り。2ペンスと1ペンスの組み合わせで2ポンドを作る組み合わせ(2ペンスを0個使う、つまり1ペンスだけの組み合わせも含める)は
sum [f1 (n - x) | x <- [0,2..n]]通り…と全ての組み合わせを洗い出す。何故これで組み合わせ総数が出るかというと、
2ペンスを0個、残りは1ペンスだけで2ポンドを作る組み合わせは
f1 200、2ペンスを1個(2ペンス)、残りは1ペンスだけで2ポンドを作る組み合わせは
f1 (200-2)、2ペンスを2個(4ペンス)、残りは1ペンスだけで2ポンドを作る組み合わせは
f1 (200-4)…なので、それらの sum を取ればよいことになる。
補足3
この辺を参考に。これは euler31-3.hs の変形。
euler31-3.hs で
f1、f2_1…と順番にやっていた処理を再帰で行うようにした。終了条件は、作りたい数200が最後の要素nで割り切れれば
そのnだけの組み合わせで200を作れるので組み合わせ総数に1を足し、
そうでなければそのnだけでは200を作れないので0を返す。
補足4
この辺やこの辺を参考に。euler31-4.hs を更に発展させた形。
まず
let ns' = zip ns $ scanr1 gcd nsで、右の要素からの最大公約数とのタプルのリストを作っておき、再帰の終了条件の中に、作りたい数200がその最小公倍数で割り切れなければ
その後の要素のみの組み合わせで200が作れないことが分かっているので0を返す、というものを追加した。