先把题目再抄一遍:
这周的题目是找零钱,假设我们需要找给别人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 make_change(amount, coins = [25, 10, 5, 1])
-
-
end
这个方法应该返回最优化的结果,即总的零钱个数最少。
另外,为了编程方便,这里假设coins已经是排序完毕的,并且如果无解的话,返回nil: make_change(5, coins = [4,2]) => nil
首先能够想到的思路是这样的:我需要把这个工作分为两个阶段,首先找出所有可能的找零方式,然后返回其中符合要求的一组。我们可以先把所需方法的架子搭起来。
-
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
这其中还是有一个思维跳跃的地方的。通过观看题目,我发现一个现象,找零钱这件事情,未必是先捡最大的零钱来用,就会得到最优解。因此,我直觉这个最优解的查找,可能相当困难,因此,第一步解题,就首先考虑穷举法,把所有可能的答案找出来,然后再进行比较,这样才不会给出错误的结果。
当然,我这样的直觉,虽然正确,却并无缘由,要等我们在随后谈到一些较为数学的内容时,再来讨论。
五一期间,外出度假,先写这点吧~~~
分享到:
相关推荐
ssd1-quiz 选择题答案 本人做的不一定满分
SSD1 Practical Quiz 答案 SSD1 Practical Quiz 答案 SSD1 Practical Quiz 答案
ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1 ssd3 practical quiz 1
四川大学操作系统quiz1 操作系统 精髓与设计原理 第五版
ssd5 Multiple choice quiz1 答案
ssd6 practical quiz 1 solution
U1 Language Quiz.docx
ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1
SSD2 Multiple-Choice Quiz 1
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
ssd3 Practical Quiz 7 答案 ssd3 Practical Quiz 7 答案
SSD7 全部QUIZ答案,包含卡耐基梅隆网站上的全部quiz答案。想要选择题答案的看过来
Best of Ruby Quiz
卡耐基 SSD1 multi-choice、quiz、exam答案
ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3
卡耐基教程SSD3 quiz3的答案 卡耐基教程SSD3 quiz3的答案
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7
SSD4完整的Quiz答案,可做考试前的复习资料
ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2