top page > computer > haskell > web_lecture > for_programmer > moneys.html
更新日:
文責: 重城良国

支払いのしかたは何通り?

(工事中 0%)

205円を作る

きっかり205円を作るには何通りの組み合わせがあるだろうか。

かなりの数の組み合わせがありそうだ。これを再帰を使って考えてみよう。

どう考えるか

単純だが巧妙な再帰的な考えかたがある。

基底部

今回は基底を3つ考える。組み合わせの数は

となる。

再帰部

100円玉、50円玉、10円玉、5円玉、1円玉の5種類の通貨で205円を作る組み合わせの数は

との和である。「すくなくとも1枚の100円玉を使って205円を作る組み合わせの数」は「5種類の通貨で105円を作る組み合わせの数」に等しい。「5種類の通貨で105円を作った」状態を考えてみよう。そのなかには100円を使っているものも使っていないものもある。そのすべてに100円を追加してやれば「すくなくとも1枚の100円玉を使って205円を作る」組み合わせができる。

どれかの基底へ

再帰によってどれかの基底に近づいていくことを説明する。「すくなくとも1枚のm円玉を使ってa円にする組み合わせ」は「a - m円をつくるすべての組み合わせ」と等しいのでm円ぶん金額が減少する。「m円玉を使わない組み合わせ」は使える通貨が減少する。金額か使える通貨のどちらかが減少するので最終的にはどれかの基底に到達する。

コード

引数と返り値

金額と使える通貨の2つの値を変化させながらの再帰的定義である。求める関数の引数と返り値は以下のようになるだろう。

金額の表現と組み合わせの数にInteger型の値を使うことにする。

changes :: [Integer] -> Integer -> Integer

基底部

change _ a | a < 0 = 0
change _ 0 = 1
change [] _ = 0

再帰部

change ma@(m : ms) a = change ma (a - m) + change ms a

自分用のコメント

この例題はもっとあとじゃないとだめだ。パターンマッチでの@の使用はトリビアルなことだからいいけど、リストをけずっていく再帰のしかたについてはもっとあとで学ぶ。関数foldrやfoldlで表現できない例として紹介するべきだろう。それとメモ化によってO(2^n)からO(m * n)くらいまで実効効率を改善できるはずだ。メモ化の例として出したほうが良いかもしれない。

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics