人気ブログランキング | 話題のタグを見る

金種計算

Haskell で金種計算をやってみた。

ある額面に対し、どういう金種をいくら用意すればよいかという問題だ。

アルゴリズムとしては、まず、与えられた額面に対し最も大きな額の金種をいくつ用意するかを計算する。これには、div 関数を使う。たとえば589円の額面に対し最も大きな額の金種が100円だったとすると、次の計算で必要な100円の枚数が5枚であることがわかる。

*Main> div 589 100
5

このとき、残りの金額は mod 関数を使って次のように計算できる。

*Main> mod 589 100
89

589円に対し100円玉を5枚用意すると残りは89円になる。そこで、この89円に対し今度は50円玉が何枚必要かを計算するというように上の計算を繰り返す。これを金種がなくなるまで繰り返す。Haskell でプログラムすると次のようになる。

kinsyu _ [] = []
kinsyu g (x:xs) = (x, g `div` x) : kinsyu (g `mod` x) xs

実行例は次のようになるが、わかっていても上のような抽象的なプログラムでちゃんと実行できていると不思議な気がする。操作の繰り返しを再帰的手続きとしてとらえることができる問題は、Haskell を使うと簡潔に記述することができる。

*Main> kinsyu 589 [100,50,10,5,1]
[(100,5),(50,1),(10,3),(5,1),(1,4)]
by tnomura9 | 2011-10-29 07:12 | Haskell | Comments(0)
<< リボ払い 級数 >>