分类：Quiz

接着上回的讨论，我们需要写两个方法，一个找出所有的零钱组合，get_all_change_list。另一个从中再找出符合要求的一个解。

找出符合要求的解，比较简单，先写在下面。
[cc lang=”ruby” css=”no”]
def get_best_change(change_list)
best_change=nil
min_length=100000
change_list.each do |list|
if list.lengthcoin
sub_change_list=get_all_change_list(amount-coin,coins)
sub_change_list.each do |list|
change_list.insert(-1,list.insert(-1,coin).sort)
end
end
if amount==coin
change_list.insert(-1,[coin])
end
end
return change_list
end
[/cc]

还有一种做加法的思路，是从所有硬币能够完成的组合来罗列。假设[25,10,5,1]这样一个组合，那么一枚硬币的组合方式，就只有4中，分别是[25],[10],[5],[1]，那么两枚硬币的组合方式自然就是，[25,25],[25,10],[25,10]….[1,5],[1,1]。一共16种，取掉次序不同的，一共有10种。再给出所有零钱组合的基础上，再寻找符合amount的找零组合即可。代码如下：

[cc lang=”ruby” css=”no”]
def get_all_change_list(amount,coins)
min_coin=coins[coins.length-1]
max_list_size=amount/min_coin+ ((amount%min_coin==0) ? 0 : 1)
change_list={}
coins.each do |coin|
change_list[[coin]]=coin
end
2.upto(max_list_size) do
new_change_list={}
coins.each do |coin|
change_list.each do |list,v|
new_change_list[list.clone.insert(list.length,coin).sort]=v+coin if v+coin<=amount end end change_list.merge!(new_change_list) end change_list.delete_if { |key,value| value!=amount } change_list.keys end [/cc] 写出这两个函数，也不容易，具体的思路，明天再讲解吧。未完待续。。。

先把题目再抄一遍：

这周的题目是找零钱，假设我们需要找给别人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]

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

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

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

自从Quake Wang在JavaEye贴出第一个Ruby每周一测之后，我就一直非常的感兴趣。不只是对题目本身很感兴趣，更觉得这是一个非常好的技术写作的架子，可以有很多个深入探索的方向。

首先是解题思路本身，就值得讲一个又一个有趣的故事。再联系到具体的语言实现，不同的语言各有巧妙不同，又值得大书特书。再有就是效率的提升，巧妙的实现是一个方面，性能的提升，则是另一个非常重要的领域。再加上举一反三，融会贯通，可以借此做语言比较，也可以借此谈语法设计的优劣，总之，每一个Quiz，都可以挖一个大坑，慢慢展开。

所以，我的手一直很痒，想拿这样的题目来下手，但是，另一方面，我的水平，又远远达不到写这样一个题目的层次，一次次提起了笔，又一次次放下~~~

最终，我还是觉得至少应该开始这件事情，能不能做完，没法保证，能不能做好，更是心里没底。只能希望各位走过路过，多多批评指正了。

未完待续…