接着上回的讨论,我们需要写两个方法,一个找出所有的零钱组合,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
-
best_change=list
-
min_length=list.length
-
end
-
end
-
return best_change
-
end
至于找到所有的解,就比较麻烦,从思路上来说,可以有两个方向,一个是做减法,一个是做加法。所谓减法,就是假设需要兑换15元的零钱,我就先考虑第一个硬币用10元,接下来就求解剩下5元的找零解法。这就是一个非常自然的,递归求解的思路。代码如下:
-
def get_all_change_list(amount,coins)
-
change_list=[]
-
coins.each do |coin|
-
if amount>coin
-
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
还有一种做加法的思路,是从所有硬币能够完成的组合来罗列。假设[25,10,5,1]这样一个组合,那么一枚硬币的组合方式,就只有4中,分别是[25],[10],[5],[1],那么两枚硬币的组合方式自然就是,[25,25],[25,10],[25,10]….[1,5],[1,1]。一共16种,取掉次序不同的,一共有10种。再给出所有零钱组合的基础上,再寻找符合amount的找零组合即可。代码如下:
-
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
写出这两个函数,也不容易,具体的思路,明天再讲解吧。未完待续。。。
分享到:
相关推荐
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
【标题】"ssd3 practical quiz2"是一个与软件工程相关的实践测验,可能是课程"Software System Development 3"(SSD3)的一部分。这个测验可能涉及了软件开发过程中的实际操作和问题解决,旨在检验学生在项目管理和...
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
### SSD2 Quiz 答案解析 #### 多选题解析1 **题目:** 下列关于计算机的陈述哪些是正确的? - 它们接受输入。 - 它们存储数据。 - 它们产生输出。 A. 只有 II B. 只有 II 和 III C. 只有 I 和 III D. I、II 和 ...
"Quiz 2答案"则表明这是一个关于SSD3的第二轮测验的答案集。虽然没有提供具体的题目或答案内容,我们可以根据SSD3的主题来探讨固态硬盘(SSD)的一些核心知识点。 固态硬盘(SSD)是一种非易失性存储设备,使用固态...
在这个“U2 Language Quiz.docx”中,我们看到了一个语言测试,主要考察的是词汇理解和句子结构。以下是每个问题解析及涉及的知识点: 1. 我发现自从我上次离开以来,这个社区已经经历了巨大的变化。 正确答案:B....
ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3
2. **封装**:封装是面向对象编程的基石之一,它涉及隐藏实现细节并提供公共接口来访问对象。在Quiz 4中,可能会有设计具有私有和公有成员的类,以及如何通过公共方法正确访问和修改数据的题目。 3. **继承**:继承...
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
### SSD7全部QUIZ quiz 答案解析 #### 多选题 Quiz1 ##### 题目1:电子商务系统由以下组件组成。哪些相同的组件必须包含在一个数据库中? 选项: - (a) I, II 和 III - (b) I 和 II - (c) I - (d) II **解析:** ...
2. **闪存的编程和擦除**:闪存单元在写入新数据前必须先进行擦除操作,这个过程比编程(写入)慢得多。因此,SSD在设计时需要考虑如何高效地管理擦除和编程操作,以避免频繁的全盘擦除。 3. **损耗平衡**:由于...
ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8
ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1 ssd3 practical quiz 1
2. **设计模式**:设计模式是解决常见软件设计问题的标准方法。 Quiz 4可能包含关于结构型(如工厂模式、代理模式)或行为型(如观察者模式、策略模式)设计模式的问题。 3. **软件架构**:这部分可能考察如何构建...
### SSD4 Quiz知识点详解 #### Fitts's Law与用户界面设计 Fitts's Law是一种预测人类在指向目标时所需时间的模型,这在人机交互领域具有重要意义。根据Quiz1的第一题,正确答案是选项(b),指出指向目标所需的时间...
2. **接口设计**:良好的接口设计是确保模块间协作无误的基础。Quiz9可能涉及如何定义输入/输出接口,以及如何处理异常和错误情况。接口设计应遵循最小惊讶原则,即用户或其他模块对接口的行为应有预期。 3. **数据...
2. **设计模式**:Quiz 7可能考察了常见的设计模式,如工厂模式、单例模式或观察者模式,要求学生理解其应用场景和优缺点。 3. **软件架构**:这可能涉及系统架构的选择,比如三层架构、微服务架构,以及如何评估...
2. **接口类型**:SSD3通常采用SATA、PCIe或M.2等接口,其中PCIe(特别是NVMe协议)提供更高的带宽和更低的延迟,使得数据传输速度远超SATA SSD。 3. **TRIM与GC(Garbage Collection)**:TRIM是SSD3的一项重要...
【ssD3 实践测验2答案解析】 在ssD3(可能指的是某种软件、框架或技术的第三阶段)的实践测验2中,我们将会深入探讨一系列与该主题相关的关键知识点。以下是对这些测试问题及其答案的详细解析: 1. **ssD3基础知识**...
### SSD4Multiple-Choice Quiz 2答案解析 #### 题目1:Option Explicit On声明的作用 - **题目描述**:在表单的通用声明部分使用`Option Explicit On`语句会导致Visual Basic如何表现? - **选项分析**: - (a) 将...