次のような問題を考えてみましょう: 千円を両替して崩す方法は何通りあるだろうか.ただし,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って良いものとする. まず問題を一般化し,つぎのように考えます.によって「円を一円玉で崩す方法の数」を表すことにします.(と言ってもならば常になのですが). また,によって「円を一円玉と五円玉で崩す方法の数」を, によって「円を一円玉と五円玉と十円玉で崩す方法の数」を, によって「円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を, によって「円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を, 最後にによって「円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします. このように定式化すると,クイズの答えはと表されます.あとはこの具体的な数値を求めれば良いわけです. さて,はを「n
![千円を崩す方法(Haskell)](https://cdn-ak-scissors.b.st-hatena.com/image/square/8d71ff5111e05619a10d29bb40d7aebaa75c8fbc/height=288;version=1;width=512/https%3A%2F%2Fs0.wp.com%2Fi%2Fblank.jpg)