151219

Ruby

Frobeniusの硬貨交換問題(1)

http://6626.teacup.com/shochandas/bbs/11882
上記において、Frobenius数を求めていたのでそのコードを書いてみた。

def f(ary)
  s_ary = Array.new(ary.max, 0)
  s_ary[-1] = 1
  a = 0
  b = s_ary.inject(:*)
  while b == 0
    f_max = a if s_ary[-1] == 0
    a += 1
    s_ary << ary.inject(0){|s, i| s += s_ary[-i]}
    s_ary.shift
    b = s_ary.inject(:*)
  end
  f_max
end

p f([4, 5, 11])
p f([5, 6, 7])
p f([3, 4, 5])
p f([3, 5, 7])
p f([3, 7, 8])
p f([3, 7, 11])
p f([14, 17, 19])

出力結果
7
9
2
4
5
8
77