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

Play with Quiz — 找零钱 (1)

阅读更多

先把题目再抄一遍:

这周的题目是找零钱,假设我们需要找给别人39美分的零钱,那么结果将会是(美元的硬币有25,10,5,1这种):

  1. >>make_change(39)  
  2. =>[25, 10, 1, 1, 1, 1] 

假设我们的硬币种类有10,7,1,那么找14美分的零钱结果将会是:

  1. >>make_change(14, [10, 7, 1])  
  2. =>[7, 7] 

这次的每周一测就是完成该方法:

  1. def make_change(amount, coins = [25, 10, 5, 1])  
  2.  
  3. end

这个方法应该返回最优化的结果,即总的零钱个数最少。
另外,为了编程方便,这里假设coins已经是排序完毕的,并且如果无解的话,返回nil: make_change(5, coins = [4,2]) => nil

首先能够想到的思路是这样的:我需要把这个工作分为两个阶段,首先找出所有可能的找零方式,然后返回其中符合要求的一组。我们可以先把所需方法的架子搭起来。

  1. def get_all_change_list(amount,coins)
  2.  
  3. end
  4.  
  5. def get_best_change(change_list)
  6.  
  7. end
  8.  
  9. def make_change(amount, coins = [25, 10, 5, 1])  
  10.   change_list=get_all_change_list(amount,coins)
  11.   get_best_change(change_list)
  12. end

这其中还是有一个思维跳跃的地方的。通过观看题目,我发现一个现象,找零钱这件事情,未必是先捡最大的零钱来用,就会得到最优解。因此,我直觉这个最优解的查找,可能相当困难,因此,第一步解题,就首先考虑穷举法,把所有可能的答案找出来,然后再进行比较,这样才不会给出错误的结果。

当然,我这样的直觉,虽然正确,却并无缘由,要等我们在随后谈到一些较为数学的内容时,再来讨论。

五一期间,外出度假,先写这点吧~~~

1
4
分享到:
评论
2 楼 kdekid 2008-05-03  
上面的算法有点小错。改正了一下。
def make_change(amount, coins=[25, 10, 5, 1])
begin
  plan = []
  for am in coins.min..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in coins.min..am/2 do
        if plan[a] and plan[am-a] then
          s = plan[a].length + plan[am-a].length
          if s < size then
            size = s
            plan[am] = plan[a] + plan[am-a]
          end
        end
      end
    end
  end
  plan[amount]
rescue StandardError => bang
  nil
end
end

1 楼 kdekid 2008-05-02  
这是个动态规划问题。
def make_change(amount, coins=[25, 10, 5, 1])
  plan = []
  for am in 1..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in 1..am/2 do
        s = plan[a].length + plan[am-a].length
        if s < size then
          size = s
          plan[am] = plan[a] + plan[am-a]
        end
      end
    end
  end
  plan[amount]
end

相关推荐

    ssd1-quiz全套答案

    在做SSD1的Quiz时,理解以上这些概念是非常关键的。通过解答选择题,学生可以检查自己的理解是否准确,找出知识盲点,并进一步深入学习。虽然这个答案集可能不保证满分,但它仍然能作为一个有效的自我评估工具,帮助...

    ssd3 practical quiz 1

    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 ssd4 practical Quiz1 PrQ1

    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

    操作系统quiz 1

    以上就是操作系统Quiz 1中涉及的一些核心知识点,涵盖了操作系统的基本功能、中断处理、内存层次结构以及计算机系统结构等方面的内容。这些基础知识对于理解和分析操作系统的工作原理至关重要。

    U1 Language Quiz.docx

    1. "exhorted" 表示强烈劝告或鼓励,而"He exhorted his companions, ‘Try to ____ your aim with diligence.’" 这句话中,我们需要一个与“目标”搭配且表示实现或完成的动词。选项B "accomplish" 正确,意为完成...

    SSD2 Multiple-Choice Quiz 1

    SSD2 Multiple-Choice Quiz 1 本资源摘要信息是基于 SSD2 Multiple-Choice Quiz 1 的问题和答案,旨在帮助用户更好地理解计算机基础知识。 问题 1:计算机处理数据的设备 计算机处理数据的设备是 CPU(Central ...

    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

    SSD1 Practical Quiz 答案

    SSD1(Solid State Drive 1)实践测验答案涵盖了固态硬盘的基础知识,包括其工作原理、优势、性能指标以及在计算机系统中的应用。在这个测验中,可能涉及了以下知识点: 1. 固态硬盘(SSD)与传统硬盘(HDD)的区别...

    SSD3-quiz4

    1. **类与对象**:理解类作为对象模板的角色,以及如何定义属性(数据成员)和方法(行为)。同时,创建和初始化对象,以及使用对象进行交互是Quiz 4的重点。 2. **封装**:封装是面向对象编程的基石之一,它涉及...

    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 答案

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

    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 quiz3答案

    1. **SSD基础架构**:固态硬盘由控制器、闪存颗粒和缓存组成。控制器负责管理读写操作、错误校正和磨损均衡等任务;闪存颗粒存储数据,分为SLC(单层单元)、MLC(多层单元)、TLC(三层单元)和QLC(四层单元),...

    SSD 4 Quiz答案

    根据Quiz1的第一题,正确答案是选项(b),指出指向目标所需的时间与目标的距离直接相关。这一原理强调了用户界面设计中元素放置的重要性,例如,将常用功能放置在容易到达的位置,可以提高用户的操作效率。Fitts's ...

    ssd3 practical quiz 8

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

    ssd3 quiz4答案

    1. **需求工程**:这是软件开发的起始阶段,包括需求获取、分析、规格化和验证。在Quiz 4中,可能会有与需求文档编写、用例描述或用户故事相关的问题。 2. **设计模式**:设计模式是解决常见软件设计问题的标准方法...

    ssd3 quiz9答案

    1. **模块化设计**:在Quiz9中,可能会考察如何将一个大系统分解为小的、可管理的模块。模块化设计是提高软件可读性、可维护性和复用性的关键。每个模块应有单一的功能,并且与其他模块之间的接口清晰明确。 2. **...

    ssd3 Practical Quiz 7 答案

    1. **工作原理**:SSD3的核心是NAND闪存,它由存储单元和控制器组成。与传统的机械硬盘(HDD)不同,SSD3没有移动部件,数据通过电子方式在闪存芯片中读写,提供了更快的访问速度和更高的耐用性。 2. **接口类型**:...

    ssd3 quiz6答案

    1. 数据结构: - 栈与队列:作为基础的数据结构,它们在Quiz 6中可能会出现。栈遵循后进先出(LIFO)原则,而队列遵循先进先出(FIFO)原则。了解它们的工作原理和应用场景至关重要。 - 树与图:Quiz 6可能包含...

Global site tag (gtag.js) - Google Analytics