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

Haskell で Project Euler を解く素人遊び

Problem 76

100を2つ以上の整数の和で表現する方法は何通りあるか

 真正面から正直にぶつかっても解けそうだが、現実的には計算量の壁に阻まれて答えは出ない。一方、これは数学で言う「分割数」の問題だと見れば、分割数の漸化式を利用する解法もありそうだ。

 しかしここは Problem 31 を思い出そう。両替問題である。

mitstream.hatenablog.jp

 Problem 31 は2£を両替する方法は何通りあるかを問う問題で、使える硬貨は一般的なものが指定されていた。Problem 76 は100円を1円玉から99円玉という硬貨を用いて何通りに両替できるかという問題と同義である。従って、Problem 31 のコードを変更せずに丸々使える。

コードを使い回すのも大切☆