プログラムでの疑問
以前自動販売機での金種の投入方法で
[500,100,50,10]円硬貨で1000円を支払う方法が158通り
[500,100,50,10,5]円硬貨では4908通り
[500,100,50,10,5,1]円硬貨では248908通り
が可能であることを見つけて貰っていたんですが
これをプログラムを使って求められないかとRubyのソフトを用いて
@cnt = 0
def change(target, coins, usable)
coin = coins.shift
if coins.size == 0 then
@cnt += 1 if target / coin <= usable
else
(0..target/coin).each{|i|
change(target - coin * i, coins.clone, usable - i)
}
end
end
change(1000, [500, 100, 50, 10], 100)
puts @cnt
から
158が入手でき
change(1000, [500, 100, 50, 10, 5], 200)
puts @cnt
から
4908が
change(1000, [500, 100, 50, 10, 5, 1], 1000)
puts @cnt
から
248908が計算できました。
そこで[6, 4, 3, 2]で12を重複を許して支払おうとするとき
change(12, [6, 4, 3, 2], 6)
で求まるはずだと実行すると
16
を返してきた。
明らかに
6+6,6+4+2,6+3+3,6+2+2+2,4+4+4,4+4+2+2,4+3+3+2,4+2+2+2+2,3+3+3+3,3+3+2+2+2,2+2+2+2+2+2
の11通りしかないので、上3つが正確に返すのに対しなぜこれが誤った結果を返してくるのか
原因が分かりません。
プログラムの作り方は見よう見まねでやっているので詳しいことが分かりません。
詳しい方教えて下さい。
[6, 4, 3, 1]で12を重複を許して支払おうとするときに、16通りになりますね。偶然？
1000,[500,100,50,10],100のようなケースでは
500と100と50をいくつずつ使っても必ず残りが10で割り切れますので
（つまり最小以外の数(500,100,50)がすべての最小の数(10)で割り切れる）
if target / coin <= usable
で問題が起こりませんが、
12,[6,4,3,2],6のように最小の2で割り切れない数があると
targetが2で割り切れない場合でも
@cnt += 1
が実行されてしまうと思います。
つまり、3が奇数個使われて最後にtargetが奇数になる
6+3+2
4+4+3
4+3+2+2
3+2+2+2+2
3+3+3+2
の5個（すべて1不足）が余計に数えられてしまっているのでしょう。
「if target / coin <= usable」
を
「if targetがcoinで割り切れ、かつtarget / coin <= usable」
に修正すれば正しく動くと思います。
（Rubyの文法を知りませんので言葉で書きました）
らすかるさんの仰る通りなのでしたか。
((x^6)^2+(x^6)+1)*((x^4)^3+(x^4)^2+(x^4)^1+1)*((x^3)^4+(x^3)^3+(x^3)^2+(x^3)^1+1)*((x^2)^6+(x^2)^5+(x^2)^4+(x^2)^3+(x^2)^2+(x^2)^1+1)
を展開して x^11 の項の係数が 5 だとチラと頭をよぎったのですが
《targetが奇数》となることをプログラムから読み取れませんでした。残念な私。
