[心得] 換零錢問題
再次獻醜了，這是換零錢的問題的練習：
amounts = ARGV.map(&:to_i)
levels = [1000,500,100,50,10,5,1]
levels.each {|level| printf("%4d,",level)}
print("\n")
amounts.each do |amount|
levels.each do |level|
q=0
if(level <= amount)
q,amount = amount.divmod level
end
printf("%4d,",q)
end
print("\n")
end
一次輸入一連串的數字，能夠列出每串數字需要的硬幣數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.29.185.99
→
04/27 13:39, , 1F
04/27 13:39, 1F
→
04/27 15:00, , 2F
04/27 15:00, 2F
推
05/02 12:01, , 3F
05/02 12:01, 3F
→
05/02 12:01, , 4F
05/02 12:01, 4F
→
05/02 12:02, , 5F
05/02 12:02, 5F
做了個用動態規劃的函數，現在用 5,4,2,1 來換 8 就沒問題了
amounts = ARGV.map(&:to_i)
$denominations = [5,4,2,1]
def change(amount)
min_number = [0] #min coin count for [index] amount
min_first_element = [] #first element of min coin set for [index] amount
for p in 1..amount
min_coin = amount #amount is the max coins changes
coin = nil
$denominations.find_all{|i| i<=p}.each{|denomination|
if (1+min_number[p-denomination]) <= min_coin
min_coin = 1+min_number[p-denomination]
coin = denomination
end
}
min_number[p] = min_coin
min_first_element[p] = coin
end
a = amount
for i in 1..min_number[amount]
printf("%4d,",min_first_element[a])
a -= min_first_element[a]
end
end
※ 編輯: markmcm 來自: 163.29.185.99 (05/05 16:16)
Ruby 近期熱門文章
PTT數位生活區 即時熱門文章
