接着上回的讨论,我们需要写两个方法,一个找出所有的零钱组合,get_all_change_list.另一个从中再找出符合要求的一个解.
找出符合要求的解,比较简单,先写在下面.
这周的题目是找零钱,假设我们需要找给别人39美分的零钱,那么结果将会是(美元的硬币有251051这种):
假设我们的硬币种类有1071,那么找14美分的零钱结果将会是:
这次的每周一测就是完成该方法:
这个方法应该返回最优化的结果,即总的零钱个数最少.
首先能够想到的思路是这样的:我需要把这个工作分为两个阶段,首先找出所有可能的找零方式,然后返回其中符合要求的一组.我们可以先把所需方法的架子搭起来.
这其中还是有一个思维跳跃的地方的.通过观看题目,我发现一个现象,找零钱这件事情,未必是先捡最大的零钱来用,就会得到最优解.因此,我直觉这个最优解的查找,可能相当困难,因此,第一步解题,就首先考虑穷举法,把所有可能的答案找出来,然后再进行比较,这样才不会给出错误的结果.
当然,我这样的直觉,虽然正确,却并无缘由,要等我们在随后谈到一些较为数学的内容时,再来讨论.
五一期间,外出度假,先写这点吧~~~
自从Quake Wang在JavaEye贴出第一个Ruby每周一测之后,我就一直非常的感兴趣.不只是对题目本身很感兴趣,更觉得这是一个非常好的技术写作的架子,可以有很多个深入探索的方向.
首先是解题思路本身,就值得讲一个又一个有趣的故事.再联系到具体的语言实现,不同的语言各有巧妙不同,又值得大书特书.再有就是效率的提升,巧妙的实现是一个方面,性能的提升,则是另一个非常重要的领域.再加上举一反三,融会贯通,可以借此做语言比较,也可以借此谈语法设计的优劣,总之,每一个Quiz,都可以挖一个大坑,慢慢展开.
所以,我的手一直很痒,想拿这样的题目来下手,但是,另一方面,我的水平,又远远达不到写这样一个题目的层次,一次次提起了笔,又一次次放下~~~
最终,我还是觉得至少应该开始这件事情,能不能做完,没法保证,能不能做好,更是心里没底.只能希望各位走过路过,多多批评指正了.