论坛首页 编程语言技术论坛

Ruby每周一测 - 找零钱

浏览 26610 次
精华帖 (4) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2008-03-25  
Ruby每周一测 - Ruby Quiz 是Ruby Talk邮件列表上的一个持续了很长时间活动,每周有一个小题目被提出来,然后大家进行解答讨论。Amazon上还有相关的书: Best of Ruby Quiz。我尝试挑选其中的一些题目进行翻译,做一个每周一测系列,欢迎大家参与讨论。

-----题目分割线-----

这周的题目是找零钱,假设我们需要找给别人39美分的零钱,那么结果将会是(美元的硬币有25,10,5,1这种):
>> make_change(39)
=> [25, 10, 1, 1, 1, 1]


假设我们的硬币种类有10,7,1,那么找14美分的零钱结果将会是:
>> make_change(14, [10, 7, 1])
=> [7, 7]


这次的每周一测就是完成该方法:
def make_change(amount, coins = [25, 10, 5, 1])

end


这个方法应该返回最优化的结果,即总的零钱个数最少。
另外,为了编程方便,这里假设coins已经是排序完毕的,并且如果无解的话,返回nil: make_change(5, coins = [4,2]) => nil


-----解答分割线-----
原题和一些解法在这里:http://rubyquiz.com/quiz154.html
原文的解答说明简单翻译见:http://www.iteye.com/post/501439
   发表时间:2008-03-25  
贴一个solution, 不是最优
def make_change(money, changes=[25,10,5,1])
  already = []
  make_change_interal(money, changes, already)
  return already
end
def make_change_interal(money, changes, already)
  #decide if we can directly change money for changes
  if changes.include?(money)#money == changes[0]
    return already.push(money) #aleady the most optimal solution
  else
    #try each changes one, which larger than money
	to_try = changes.select {|x| x < money}
	#puts "to_try is #{to_try.inspect}"
	if to_try.size == 0 #&& money !=0 , we failed
	  return false
	end
	max = 9999
	#should backup the already, backtrace if necessary.
	change = changes[0]
	already_backup = already.dup
	 to_try.each do |x|
	  already0 = already_backup.dup
	  if make_change_interal(money - x, changes, already0.push(x))
	    if max > already0.size
		  
		  max = already0.size
		  already.replace(already0) #etc.
		  #change = x
		  #puts "max is #{max}, already0 is #{already0.inspect}"
		end
	  end
	  #and compare the result size. #and should cut out which definitely impossible route.
	end
	
    return true
  end
end
p make_change(25) #=>[25]
p make_change(10) #=>[10]
p make_change(1) #=>[1]
p make_change(39) #=> [25, 10, 1, 1, 1, 1] 

p make_change(26)
p make_change(27)
p make_change(14, [10, 7, 1])   
0 请登录后投票
   发表时间:2008-03-25  
我也贴一个上来。

def make_change(amount, coins = [25, 10, 5, 1])
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount,1)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin})
    if min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  min_one_coin ? [min_one_coin]+min_coins : min_coins
end

p make_change(39)
p make_change(14, [10, 7, 1])
0 请登录后投票
   发表时间:2008-03-25  
老庄的方法跑 make_change(14, [5,3,2]) 会出错
0 请登录后投票
   发表时间:2008-03-25  
对的,通常的找零钱,一定会有解,所以一定会有一个1。

如果你的零钱中,最小的是2,那么输入1,就肯定会错。

比如 make_change(5,[7,2])

这样的题目,本身就是错的。
0 请登录后投票
   发表时间:2008-03-25  
嗯,假如无解的话,可以返回nil,我已经修改题目,添加了这个说明
但是make_change(14, [5,3,2]) 是有解的,只是你那个解法算出来的不正确。
0 请登录后投票
   发表时间:2008-03-25  
修订版

def make_change(amount, coins = [25, 10, 5, 1])
  return [amount] if coins.include?(amount)
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin})
    if other_coins && min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  min_one_coin ? [min_one_coin]+min_coins : nil
end
0 请登录后投票
   发表时间:2008-03-25  
凑个热闹,错误的贪心法!


def make_change(account, coins = [25, 10, 5, 1])
	solution = []
	current_account = account
	coins.each { |coin|
	
		break if current_account == 0
		
		if current_account >= coin
			number = current_account / coin
			current_account -= coin * number
			number.times { solution << coin }
		elsif coin == coins.last
			solution = nil
			break
		end
	}
	solution
end
0 请登录后投票
   发表时间:2008-03-25  
to:姜太公

注意:应该返回最优化的结果,即总的零钱个数最少。
并且如果无解的话,返回nil

你的程序,有bug。
0 请登录后投票
   发表时间:2008-03-26  
def make_change(amount, coins = [25, 10, 5, 1])
	change = []
	coins.each do |coin|
		(amount / coin).times do
			change << coin
			amount -= coin
		end
	end
	change if amount.zero?
end

p make_change(39) #[25, 10, 1, 1, 1, 1]
p make_change(14, [10, 7, 1]) #[10, 1, 1, 1, 1]
p make_change(14, [5, 3, 2]) #nil
p make_change(12, [22, 3, 2]) #[3, 3, 3, 3]
0 请登录后投票
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics