`
庄表伟
  • 浏览: 1150514 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Play with Quiz — 找零钱(2)

 
阅读更多

接着上回的讨论,我们需要写两个方法,一个找出所有的零钱组合,get_all_change_list。另一个从中再找出符合要求的一个解。

找出符合要求的解,比较简单,先写在下面。

  1. def get_best_change(change_list)
  2.   best_change=nil
  3.   min_length=100000
  4.   change_list.each do |list|
  5.     if list.length<min_length
  6.       best_change=list
  7.       min_length=list.length
  8.     end
  9.   end
  10.   return best_change
  11. end

至于找到所有的解,就比较麻烦,从思路上来说,可以有两个方向,一个是做减法,一个是做加法。所谓减法,就是假设需要兑换15元的零钱,我就先考虑第一个硬币用10元,接下来就求解剩下5元的找零解法。这就是一个非常自然的,递归求解的思路。代码如下:

  1. def get_all_change_list(amount,coins)
  2.   change_list=[]
  3.   coins.each do |coin|
  4.     if amount>coin
  5.       sub_change_list=get_all_change_list(amount-coin,coins)
  6.       sub_change_list.each do |list|
  7.         change_list.insert(-1,list.insert(-1,coin).sort)
  8.       end
  9.     end
  10.     if amount==coin
  11.       change_list.insert(-1,[coin])
  12.     end
  13.   end
  14.   return change_list
  15. end

还有一种做加法的思路,是从所有硬币能够完成的组合来罗列。假设[25,10,5,1]这样一个组合,那么一枚硬币的组合方式,就只有4中,分别是[25],[10],[5],[1],那么两枚硬币的组合方式自然就是,[25,25],[25,10],[25,10]….[1,5],[1,1]。一共16种,取掉次序不同的,一共有10种。再给出所有零钱组合的基础上,再寻找符合amount的找零组合即可。代码如下:

  1. def get_all_change_list(amount,coins)
  2.   min_coin=coins[coins.length-1]
  3.   max_list_size=amount/min_coin+ ((amount%min_coin==0) ? 0 : 1)
  4.   change_list={}
  5.   coins.each do |coin|
  6.     change_list[[coin]]=coin
  7.   end
  8.   2.upto(max_list_size) do
  9.     new_change_list={}
  10.     coins.each do |coin|
  11.       change_list.each do |list,v|
  12.         new_change_list[list.clone.insert(list.length,coin).sort]=v+coin if v+coin<=amount
  13.       end
  14.     end
  15.     change_list.merge!(new_change_list)
  16.   end
  17.   change_list.delete_if { |key,value| value!=amount }
  18.   change_list.keys
  19. end

写出这两个函数,也不容易,具体的思路,明天再讲解吧。未完待续。。。

2
0
分享到:
评论

相关推荐

    ssd3 practical quiz 2

    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

    【标题】"ssd3 practical quiz2"是一个与软件工程相关的实践测验,可能是课程"Software System Development 3"(SSD3)的一部分。这个测验可能涉及了软件开发过程中的实际操作和问题解决,旨在检验学生在项目管理和...

    ssd3 practical quiz 6

    ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5

    ssd2 quiz 答案

    ### SSD2 Quiz 答案解析 #### 多选题解析1 **题目:** 下列关于计算机的陈述哪些是正确的? - 它们接受输入。 - 它们存储数据。 - 它们产生输出。 A. 只有 II B. 只有 II 和 III C. 只有 I 和 III D. I、II 和 ...

    ssd3 quiz2答案

    "Quiz 2答案"则表明这是一个关于SSD3的第二轮测验的答案集。虽然没有提供具体的题目或答案内容,我们可以根据SSD3的主题来探讨固态硬盘(SSD)的一些核心知识点。 固态硬盘(SSD)是一种非易失性存储设备,使用固态...

    U2 Language Quiz.docx

    在这个“U2 Language Quiz.docx”中,我们看到了一个语言测试,主要考察的是词汇理解和句子结构。以下是每个问题解析及涉及的知识点: 1. 我发现自从我上次离开以来,这个社区已经经历了巨大的变化。 正确答案:B....

    ssd3 practical quiz 3

    ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3

    SSD3-quiz4

    2. **封装**:封装是面向对象编程的基石之一,它涉及隐藏实现细节并提供公共接口来访问对象。在Quiz 4中,可能会有设计具有私有和公有成员的类,以及如何通过公共方法正确访问和修改数据的题目。 3. **继承**:继承...

    ssd3 practical quiz 5

    ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5

    SSD7全部QUIZ quiz 答案

    ### SSD7全部QUIZ quiz 答案解析 #### 多选题 Quiz1 ##### 题目1:电子商务系统由以下组件组成。哪些相同的组件必须包含在一个数据库中? 选项: - (a) I, II 和 III - (b) I 和 II - (c) I - (d) II **解析:** ...

    ssd3 quiz3答案

    2. **闪存的编程和擦除**:闪存单元在写入新数据前必须先进行擦除操作,这个过程比编程(写入)慢得多。因此,SSD在设计时需要考虑如何高效地管理擦除和编程操作,以避免频繁的全盘擦除。 3. **损耗平衡**:由于...

    ssd3 practical quiz 8

    ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8

    ssd3 practical quiz 1

    ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1 ssd3 practical quiz 1

    ssd3 quiz4答案

    2. **设计模式**:设计模式是解决常见软件设计问题的标准方法。 Quiz 4可能包含关于结构型(如工厂模式、代理模式)或行为型(如观察者模式、策略模式)设计模式的问题。 3. **软件架构**:这部分可能考察如何构建...

    SSD 4 Quiz答案

    ### SSD4 Quiz知识点详解 #### Fitts's Law与用户界面设计 Fitts's Law是一种预测人类在指向目标时所需时间的模型,这在人机交互领域具有重要意义。根据Quiz1的第一题,正确答案是选项(b),指出指向目标所需的时间...

    ssd3 quiz9答案

    2. **接口设计**:良好的接口设计是确保模块间协作无误的基础。Quiz9可能涉及如何定义输入/输出接口,以及如何处理异常和错误情况。接口设计应遵循最小惊讶原则,即用户或其他模块对接口的行为应有预期。 3. **数据...

    ssd3 quiz7答案

    2. **设计模式**:Quiz 7可能考察了常见的设计模式,如工厂模式、单例模式或观察者模式,要求学生理解其应用场景和优缺点。 3. **软件架构**:这可能涉及系统架构的选择,比如三层架构、微服务架构,以及如何评估...

    ssd3 Practical Quiz 7 答案

    2. **接口类型**:SSD3通常采用SATA、PCIe或M.2等接口,其中PCIe(特别是NVMe协议)提供更高的带宽和更低的延迟,使得数据传输速度远超SATA SSD。 3. **TRIM与GC(Garbage Collection)**:TRIM是SSD3的一项重要...

    ssD3 Practical Quiz 2 答案

    【ssD3 实践测验2答案解析】 在ssD3(可能指的是某种软件、框架或技术的第三阶段)的实践测验2中,我们将会深入探讨一系列与该主题相关的关键知识点。以下是对这些测试问题及其答案的详细解析: 1. **ssD3基础知识**...

    SSD4Multiple-Choice Quiz 2答案

    ### SSD4Multiple-Choice Quiz 2答案解析 #### 题目1:Option Explicit On声明的作用 - **题目描述**:在表单的通用声明部分使用`Option Explicit On`语句会导致Visual Basic如何表现? - **选项分析**: - (a) 将...

Global site tag (gtag.js) - Google Analytics