千円を崩す方法(Haskell)

次のような問題を考えてみましょう：

千円を両替して崩す方法は何通りあるだろうか．ただし，一円玉，五円玉，十円玉，五十円玉，百円玉，五百円玉を自由に（好きなだけ）使って良いものとする．

まず問題を一般化し，つぎのように考えます．によって「円を一円玉で崩す方法の数」を表すことにします．（と言ってもならば常になのですが）．

また，によって「円を一円玉と五円玉で崩す方法の数」を，

によって「円を一円玉と五円玉と十円玉で崩す方法の数」を，

によって「円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を，

によって「円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を，

最後にによって「円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします．

このように定式化すると，クイズの答えはと表されます．あとはこの具体的な数値を求めれば良いわけです．

さて，はを「n円を五百円玉を一枚も使わないで表した場合の数」と「(n-500)円をすべてのコインを好きなだけ使って表した場合の数」の和だと考えられます．
（追記2018/08/27　少し説明を補います．円を全てのコインを使って崩した場合を全て列挙した集合をとしましょう．を (i)五百円玉を一つも含まないもの (ii)少なくとも1枚の五百円玉を含むもの　に分割できます．それぞれの場合からなる集合をとしましょう． (非交和）ですから， となります．明らかにです．の全ての要素から五百円玉を一つ抜くと，それぞれは円を崩したものになっています．したがってです．
）．よって

となります．よって，の計算をの計算に還元できます．

同様に考えれば
などの式が得られます．ただし，負のインデックスに対してははいずれもゼロとします．この考えをそのままHaskellコードにすれば次のようになります：

fA n | (n < 0) = 0
     | otherwise = 1

fB n | (n < 0) = 0
     | otherwise = fA n + fB (n-5)

fC n | (n < 0) = 0
     | otherwise = fB n + fC (n-10)

fD n | (n < 0) = 0
     | otherwise = fC n + fD (n-50)

fE n | (n < 0) = 0
     | otherwise = fD n + fE (n-100)

fF n | (n < 0) = 0
     | otherwise = fE n + fF (n-500)

これらの定義を書いてGHCiで:l 1000yen.hs してやってから fF 1000 を計算させると248908という答えが得られます．

したがって，一円玉，五円玉，十円玉，五十円玉，百円玉，五百円玉を自由に（好きなだけ）使って千円を両替する方法は全部で248908通りあることになります．

この問題はポリア他『組合せ論入門』p.11（近代科学社）で扱われている問題を改変したものです．（元の問題は１ドルを１セント，５セント，10セント，25セント，50セントで崩す問題です．）この問題はポリアのお気に入りだったのか，Pólya & Szegö “Problems and Theorems in Analysis I” にも収録されています．）

この記事では漸化式を組み合わせ論的な考えで導きましたが，ポリアの本では母関数を利用して漸化式を導いています．興味のある方は是非ポリアの『組合せ論入門』を読んでみてください．

広告

differentialengineの投稿 (2017/12/24)

https://differentialengine.wordpress.com/2017/12/24/%e5%8d%83%e5%86%86%e3%82%92%e5%b4%a9%e3%81%99%e6%96%b9%e6%b3%95haskell/