2008-05-01

Play with Quiz — 找零钱 (1)

先把题目再抄一遍：

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

  1. >>make_change(39)  
  2. =>[25, 10, 1, 1, 1, 1] 

假设我们的硬币种类有10,7,1，那么找14美分的零钱结果将会是：

  1. >>make_change(14, [10, 7, 1])  
  2. =>[7, 7] 

这次的每周一测就是完成该方法：

  1. def make_change(amount, coins = [25, 10, 5, 1])  
  2.  
  3. end

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

首先能够想到的思路是这样的：我需要把这个工作分为两个阶段，首先找出所有可能的找零方式，然后返回其中符合要求的一组。我们可以先把所需方法的架子搭起来。

  1. def get_all_change_list(amount,coins)
  2.  
  3. end
  4.  
  5. def get_best_change(change_list)
  6.  
  7. end
  8.  
  9. def make_change(amount, coins = [25, 10, 5, 1])  
  10.   change_list=get_all_change_list(amount,coins)
  11.   get_best_change(change_list)
  12. end

这其中还是有一个思维跳跃的地方的。通过观看题目，我发现一个现象，找零钱这件事情，未必是先捡最大的零钱来用，就会得到最优解。因此，我直觉这个最优解的查找，可能相当困难，因此，第一步解题，就首先考虑穷举法，把所有可能的答案找出来，然后再进行比较，这样才不会给出错误的结果。

当然，我这样的直觉，虽然正确，却并无缘由，要等我们在随后谈到一些较为数学的内容时，再来讨论。

五一期间，外出度假，先写这点吧~~~

评论
kdekid 2008-05-03   回复
上面的算法有点小错。改正了一下。
def make_change(amount, coins=[25, 10, 5, 1])
begin
  plan = []
  for am in coins.min..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in coins.min..am/2 do
        if plan[a] and plan[am-a] then
          s = plan[a].length + plan[am-a].length
          if s < size then
            size = s
            plan[am] = plan[a] + plan[am-a]
          end
        end
      end
    end
  end
  plan[amount]
rescue StandardError => bang
  nil
end
end
kdekid 2008-05-02   回复
这是个动态规划问题。
def make_change(amount, coins=[25, 10, 5, 1])
  plan = []
  for am in 1..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in 1..am/2 do
        s = plan[a].length + plan[am-a].length
        if s < size then
          size = s
          plan[am] = plan[a] + plan[am-a]
        end
      end
    end
  end
  plan[amount]
end
发表评论

您还没有登录，请登录后发表评论

庄表伟
搜索本博客
我的相册
B5998f8e-0b53-4830-ae9e-da1c6fa20ddc-thumb
匪夷所思
共 19 张
存档
最新评论