Play with Quiz — 找零钱 (1)

先把题目再抄一遍:

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

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

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

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

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

[cc lang=”ruby” css=”no”]
def get_all_change_list(amount,coins)

end

def get_best_change(change_list)

end

def make_change(amount, coins = [25, 10, 5, 1])
change_list=get_all_change_list(amount,coins)
get_best_change(change_list)
end[/cc]

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

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

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

发表评论

电子邮件地址不会被公开。