先把题目再抄一遍:
这周的题目是找零钱,假设我们需要找给别人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时,理解以上这些概念是非常关键的。通过解答选择题,学生可以检查自己的理解是否准确,找出知识盲点,并进一步深入学习。虽然这个答案集可能不保证满分,但它仍然能作为一个有效的自我评估工具,帮助...
ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1 ssd3 practical quiz 1
ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1 ssd4 practical Quiz1 PrQ1
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
以上就是操作系统Quiz 1中涉及的一些核心知识点,涵盖了操作系统的基本功能、中断处理、内存层次结构以及计算机系统结构等方面的内容。这些基础知识对于理解和分析操作系统的工作原理至关重要。
1. "exhorted" 表示强烈劝告或鼓励,而"He exhorted his companions, ‘Try to ____ your aim with diligence.’" 这句话中,我们需要一个与“目标”搭配且表示实现或完成的动词。选项B "accomplish" 正确,意为完成...
SSD2 Multiple-Choice Quiz 1 本资源摘要信息是基于 SSD2 Multiple-Choice Quiz 1 的问题和答案,旨在帮助用户更好地理解计算机基础知识。 问题 1:计算机处理数据的设备 计算机处理数据的设备是 CPU(Central ...
ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3
SSD1(Solid State Drive 1)实践测验答案涵盖了固态硬盘的基础知识,包括其工作原理、优势、性能指标以及在计算机系统中的应用。在这个测验中,可能涉及了以下知识点: 1. 固态硬盘(SSD)与传统硬盘(HDD)的区别...
1. **类与对象**:理解类作为对象模板的角色,以及如何定义属性(数据成员)和方法(行为)。同时,创建和初始化对象,以及使用对象进行交互是Quiz 4的重点。 2. **封装**:封装是面向对象编程的基石之一,它涉及...
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
#### 多选题 Quiz1 ##### 题目1:电子商务系统由以下组件组成。哪些相同的组件必须包含在一个数据库中? 选项: - (a) I, II 和 III - (b) I 和 II - (c) I - (d) II **解析:** 本题考察的是电子商务系统的组成...
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
1. **SSD基础架构**:固态硬盘由控制器、闪存颗粒和缓存组成。控制器负责管理读写操作、错误校正和磨损均衡等任务;闪存颗粒存储数据,分为SLC(单层单元)、MLC(多层单元)、TLC(三层单元)和QLC(四层单元),...
根据Quiz1的第一题,正确答案是选项(b),指出指向目标所需的时间与目标的距离直接相关。这一原理强调了用户界面设计中元素放置的重要性,例如,将常用功能放置在容易到达的位置,可以提高用户的操作效率。Fitts's ...
ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8
1. **需求工程**:这是软件开发的起始阶段,包括需求获取、分析、规格化和验证。在Quiz 4中,可能会有与需求文档编写、用例描述或用户故事相关的问题。 2. **设计模式**:设计模式是解决常见软件设计问题的标准方法...
1. **模块化设计**:在Quiz9中,可能会考察如何将一个大系统分解为小的、可管理的模块。模块化设计是提高软件可读性、可维护性和复用性的关键。每个模块应有单一的功能,并且与其他模块之间的接口清晰明确。 2. **...
1. **工作原理**:SSD3的核心是NAND闪存,它由存储单元和控制器组成。与传统的机械硬盘(HDD)不同,SSD3没有移动部件,数据通过电子方式在闪存芯片中读写,提供了更快的访问速度和更高的耐用性。 2. **接口类型**:...
1. 数据结构: - 栈与队列:作为基础的数据结构,它们在Quiz 6中可能会出现。栈遵循后进先出(LIFO)原则,而队列遵循先进先出(FIFO)原则。了解它们的工作原理和应用场景至关重要。 - 树与图:Quiz 6可能包含...