要改进这两种算法，都是一个目标，就是寻找不需要列出所有解的办法来。
前一种算法，是求出所有的可能解，然后再找其中的最优解。要进行优化，则可以将求解与求优合二为一。在每一个递归中，都寻找最优解。比如，make_change(14,[10,7,2])，我们就可以寻找14-10后剩余的4的最优解，得到[2,2]，以及14-7后剩余的7的最优解，得到[7]，最后是14-2后剩余的12的最优解，得到[10,2]。然后选择其中最短的一个[7]，组合为[7,7]作为结果返回。
代码如下：
def make_change(amount, coins = [25, 10, 5, 1])&nbs ...
接着上回的讨论，我们需要写两个方法，一个找出所有的零钱组合，get_all_change_list。另一个从中再找出符合要求的一个解。
找出符合要求的解，比较简单，先写在下面。
def get_best_change(change_list)
best_change=nil
min_length=100000
change_list.each do |list|
if list.length<min_length
...
先把题目再抄一遍：
这周的题目是找零钱，假设我们需要找给别人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 ...
自从Quake Wang在JavaEye贴出第一个Ruby每周一测之后，我就一直非常的感兴趣。不只是对题目本身很感兴趣，更觉得这是一个非常好的技术写作的架子，可以有很多个深入探索的方向。
首先是解题思路本身，就值得讲一个又一个有趣的故事。再联系到具体的语言实现，不同的语言各有巧妙不同，又值得大书特书。再有就是效率的提升，巧妙的实现是一个方面，性能的提升，则是另一个非常重要的领域。再加上举一反三，融会贯通，可以借此做语言比较，也可以借此谈语法设计的优劣，总之，每一个Quiz，都可以挖一个大坑，慢慢展开。
所以，我的手一直很痒，想拿这样的题目来下手，但是，另一方 ...
接着昨天的思考往下深入。分析一下JavaEye作为一个社区的特点。首先是有哪些人，其次是有哪些内容，然后是有哪些交流方式。以下的内容，只是一些粗略的思考，希望能够抛砖引玉。
一、人的类型
1、匆匆过客，这些人通常会通过搜索引擎而来，当然也可能是在其他的网站中看到了JavaEye的链接，在达到（或者没有达到）自己的目标之后，就会离开。现在JavaEye的相关文章推荐的水平在不断提高，这有助于这些匆匆过客，再多浏览一些页面，或者有助于他们从过客转换为常客。
2、潜水常客，这些人对JavaEye留下了明确的印象，在遇到问题（或者无聊）的时候会想到来这里看看。如果遇到有兴趣的话题，也许会注册一下 ...
今天在跟Robbin聊天，聊的话题也比较散，只能记一个大概了。背景1、最近JavaEye在很激烈的讨论关于技术书籍翻译的事情。[读书] 书评：《敏捷软件开发》中文版第二版[读书] 语无伦次的译者作者黑名单好多译者都浮出来了，还有出版社的朋友，也参与了讨论。气氛甚为热烈。背景2、这两天在博文视点出版社的Groups里，也正好在讨论一部书稿，叫做《编程新手真言》，被不少人，包括我在内，毫不留情的批评了一通。背景3、百度Hi推出体验版，采用邀请机制，一时间邀请的Blogger与想要获得邀请的帖子满天飞，热闹得不得了。背景4、SNS（国内抄袭Facebook与Myspaces的网站）大繁荣。正好Rob ...
2005年1月28日，在BlogCN安家，写了第一篇blog。2005年11月7日，告别BlogCN，迁到了MSN Spaces。blogcn link 2005年11月14日，新注册了一家BlogJava。2006年10月18日，在BlogJava发表最后一篇Blog，从此不再去了。blogjava link 自从JavaEye有了Blog以后，一直用到了现在。 自从搬到了MSN Spaces之后，从2005年4月7日一直用到了现在。msn link 还有其他零零碎碎开了没去的blog，比如BlogSpot；BlogBus；Baidu空间等等等等。&n ...
世事洞明皆学问1、儿子刚换了新的幼儿园，前两天，我们问他：“幼儿园里的老师，喜欢你吗？”，他说：“刚去了两天，我还比较乖，他们当然还是喜欢我的。等到过两天，我不乖了，他们就不喜欢我了。”2、过了两天，他在幼儿园里犯错误了，我们问他：“老师骂你了吗？”他说：“没有”；“为什么呢？”；“因为老师善良呀。” 人情练达即文章1、儿子还是很喜欢原来幼儿园的贝贝老师，常常自己拨电话打给老师。有一次，他们老师在电话里问他：“到新的幼儿园，会哭吗 ...
DynamicStruct，是我最近自己在鼓捣的一个ruby项目，这是一个更大的计划的一部分。
当他完成之后，应该是这样的一个结构：
Aurum
|
V
RubyBCL
|
V
DynamicStruct
Aurum是目前徐昊正在做的一个项目，简单的介绍可以看这里：《A very brief introduction to Aurum》
通过aurum，可以更加方便的定义新的语言。
但是，仅仅依靠aurum，只能让新设计出来的语言，运行于aurum的解释环境中，ruby就已经是够慢的解释语言了，这样的解释执行方式，可以说完全无法得到具 ...
一、吃葱聪明奶奶劝点点多吃点葱，并且告诉他：“吃葱好呀，吃了就聪明了”。于是点点就对奶奶说：“奶奶，那你应该多吃点葱呀，你到现在普通话都学不好。” 二、残酷最近点宝住在奶奶家，出于一个老教育工作者的执着，奶奶准备开始给点点教规矩了，于是对点点说：“点点，从今天起，你就要按计划，早睡早起，好好学习，少看电视了。”点点叫道：“哎呀我的妈呀，这也太残酷了吧！” 三、奶奶的幽默最近上海总是阴雨绵绵，我们全家开车出门，车子里雾得不得了，因为新贴了车膜，又不能开除雾的开关，只能不断的用纸巾去 ...
庄表伟
- 浏览: 643336 次
- 性别:
- 来自: 上海
- 详细资料
搜索本博客
我的相册
共 19 张
最近加入圈子
最新评论
-
Play with Quiz — 找零 ...
上面的算法有点小错。改正了一下。def make_change(amount, ...
-- by kdekid -
Play with Quiz — 找零 ...
这是个动态规划问题。def make_change(amount, coins= ...
-- by kdekid -
Play with Quiz (0) ...
引用我的手一直很痒，想拿这样的题目来下手，但是，另一方面，我的水平，又远远达不到 ...
-- by fuliang -
JavaEye社区再分析 ...
其实硬分成哪几类也没什么用，大家都是综合型的，也就是哪种都有。 俺被隐藏过贴，刚 ...
-- by hilliate -
小人精
幸福啊、羡慕
-- by wayer
评论排行榜