以åèªå販売æ©ã§ã®éçš®ã®æå
¥æ¹æ³ã§
[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ãå¥æ°ããšãªãããšãããã°ã©ã ããèªã¿åããŸããã§ãããæ®å¿µãªç§ã