Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

「1ドルを任意のコインに両替する組み合わせ数」を計算する(両替問題)

今日の料理

f:id:nisemono_san:20160416131418j:plain

肉きしめん

概要

なんらかの金額が与えられた場合に、それを両替するコインの組みあわせ数を求められる問題が、いわばプログラミングの基礎的な問題として使われることが多い。今回は、木構造を作るような再帰的な関数を定義し、この問題にチャレンジしたい。

はじめに

久しぶりに、基礎でもかためるか、と思ってSICPを再読しているのだけれども、その中に両替問題というものがある。これは、木構造再帰を使いながら、そのコードを使うというものである。SICPを翻訳した和田英一氏によれば、この問題はとても古典的であるらしい。少し調べてみると、類似の問題が数学オリンピックの予選に使われた記述もある。

なるほど、これらの詳しい考察については、このpdfに記載がある。また、この問題を詳しく考えると、動的計画法で解けるとした記述もある。こちらは自分のレベルではないようなので、今後の課題にしたい。

さて、今回は単純に木構造再帰で解いてみることにする。使用する言語はRubyである。

問題を分析する

まず、SICPに書いてある「50セント, 25セント, 10セント, 5 セント, 1セントがあるとして1ドルの両替にはどのくらいの場合があるか」ということを考えた場合、この問題の最小定義がどれくらいに当たるか、を考えてみる。

まず、この問題に類似するもので、最小の定義を考えてみると、恐らく「10円を、10円玉と5円玉と1円玉で組みあわせてみる」という問題だろう。これは手で書いてみればわかるように、「10円、5円と5円、5円と1円、1円」というようになるだろう。

まず、素朴に考えるならば再帰的に、10円であるパターンと5円であるパターン……といったように、どんどん絞りこんでいくパターンが存在する。

ポイントは、先のコインから徐々に下っていけばいいということになる。

例えば、10円をある枚数よりは使わないとしたならば、今後10円を候補として入れないようにすればよい。そこで、現在選別しているコインを引き数にわたすことで、その役目を与えることにしよう。

def change_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0

  sum_coin = 0
  case coin
  when 10
    sum_coin += change_node(x - 5, 5)
  end
  sum_coin += change_node(x - coin, coin) + 1
  return sum_coin
end

このコードは、自分が考えるにおいて、あまりきれいではないと感じる。なぜなら、変更に弱いことが上げられる。それは、これがループの入れ子構造になってしまうからだ。実際に、25や50など、増やしていくたびに煩雑になることは否めない。例えば、この高校教師の方が書いたサンプルプログラムを見てみよう

rem "両替問題 2004/10/25"
rem a=両替金額,c=カウンタ
LET a=500
LET c=0
let t0=time
for k5000=0 to int(a/5000)
  for k1000=0 to int(a/1000)
    for k500=0 to int (a/500)
      for k100=0 to int (a/100)
        for k50=0 to int(a/50)
          for k10=0 to int(a/10)
            for k5=0 to int(a/5)
              for k1=0 to int(a/1) step 5
                if a=1*k1+5*k5+10*k10+50*k50+100*k100+500*k500+1000*k1000+5000*k5000 then LET c=c+1
              next k1
            next k5
          next k10
        next k50
      next k100
    next k500
  next k1000
next k5000
print c
print time-t0;"秒かかりました"
end

もちろん、このコードは本職ではないため、かなり力技であることは否めない。もちろん、再帰とは反復ではあるのだが、あまり変わらないともいえる。さて、もうすこし柔軟な方法は無いものだろうか。

問題を拡張する

そこで、少し問題を拡張してみる。まず、任意の求めたい総額を{Y}と起き、利用する硬貨の数を{n_i}としたとき、{Y = 10n_10 * 5n_5 * n_1}を見たす条件のものだということが考えられる。これを満す{n_10 + n_5 + n}を求めればよい。このとき、{n_10, n_5, n_1}{Y=10}の場合を考えると、下のようになるだろう。

1, 0,  0
0, 2,  0
0, 1,  5
0, 0, 10

なので、下のように表現することが可能になる。

def change_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0

  sum_coin =
    if coin >= 50
      change_node(x - 50, 50)
    else
      0
    end +
    if coin >= 25
      change_node(x - 25, 25)
    else
      0
    end +
    if coin >= 10
      change_node(x - 10, 10)
    else
      0
    end +
    if coin >= 5
      change_node(x -  5,  5)
    else
      0
    end
end

これを見ると、繰り返し出てくる表現があることに気がつかされる。そこで、関数にくくり出してみることにする。

def change_coin x, n, coin
  if x - coin >= 0 && n >= coin
    change_node(x - coin, coin)
  else
    0
  end
end

さて、このような補助関数を作ることによって、次のようなシンプルなコードに直すことが可能になる。

def change_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0
  return change_coin(x, coin, 50) +
     change_coin(x, coin, 25) +
     change_coin(x, coin, 10) +
     change_coin(x, coin,  5) + 1
end

ここまでくると、単純な関数呼び出しになるので、Rubyたとinjectで畳みこむことが可能になる。利用するコインの数を配列とし、ブロックに渡すことで、柔軟性のあるコードとなる。

COINS = [50, 25, 10, 5]
def change_node x, coin
  return 1 if x == 0
  return 1 if x < 5
  return 0 if x < 0
  return COINS.inject(1) do |sum, c|
    sum + change_coin(x, coin, c)
  end
end

あとは、これをラップする関数を定義すればよい。

def change x
  change_node x, COIN[0]
end

メモ化

ここで気がつくのは、両替のノードを作成する上において、なんども同じパターンが出てくるということだ。なので、これをなんらかのかたちでメモしておき、もし同じ呼び出しが行なわれた場合、メモから取ってくることで計算量が押さえられるだろう。

$caches = {}
def cache_change_coin x, n, coin
  caches_key = "#{x}_#{n}_#{coin}"
  if $caches[caches_key].nil?
    if x - coin >= 0 && n >= coin
      $caches[caches_key] = change_node(x - coin, coin)
    else
      $caches[caches_key] = 0
    end
  end
  $caches[caches_key]
end

今回は連想配列を簡易メモとして使った。一度計算したノードは配列のキーに格納されるので、大きくなればなるほど改善されている。

どれくらい改善されたかというと、PDFに乗っていた「10000円の5000札、1000円札、500円玉、100円玉、50円玉、10円玉、5円玉、1円玉への両替」の「18155171408通り」を0.198228sで計算できるようになる。ちなみに、メモ化しない場合は返ってこない。

蛇足

ちなみに、これの元のプロトタイプコードに関してはRacketで書いてあるものが、gistに置いてあるので参考にどうそ。

まとめ

はっきりいって、両替問題はいまさらのような感じがするのだけれども、いまさらの問題をいまさらのように解いてみると、新しい発見があって良かった。とはいえ、上のコードに問題が無いわけではない。やはり動的計画法を利用したり、あるいはこれが等差数列になることを利用して改善を図る必要がある。これは今後の課題としたい。