同学们好。在前面一节课，我们了解了贪心算法，这节课我们来对算法做进一步的讨论。在讨论新的内容之前，我们先来回顾一下上一节课安排的课后小练习。前面我们已经讨论过了，在找零问题上我们一直在用贪心算法，也就是在找零过程中，总是使用当前面值最大的零钱，因为我们总是希望用最少的零钱数量来找零，这里的零钱数量就是我们找零的纸币和硬币的数量和。如果我们在找零过程中要求使用最多的零钱数量来找零，还能使用贪心算法吗？同学们可以回顾一下贪心算法的核心是什么？贪心算法的核心就是在解决问题的步骤中，每一个步骤都选择当前的最优解，不考虑整体。解决问题的最优解就是人们对问题最满意的解法。既然我们要求使用最多的零钱数量来找零，我们可以先从面值最小的硬币开始组合，因此可以使用贪心算法。下面给出问题的解决步骤。问题：假设有面值1角、2角、5角、10角（1元）的硬币各5枚，要求用最多的硬币数量来找零。该如何找1.3元的零钱？使用贪心算法找1.3元零钱的步骤如下：（1）选择1角硬币5枚，面值总额为5角；（2）选择2角硬币4枚，面值总额为13角，即1.3元。共需要9枚硬币。不知道同学们做过火车或地铁没有，现在火车站或地铁车站都有自动售票机。当你买好票要付款时，你可以把现金竖着放入到自动售票机的条形孔中，自动售票机会自动把现金吸取到自动售票机中，现金只能一张一张放入，现金放入完成后。自动售票机会识别你放入的现金金额，如果现金金额不足给出金额不足提示。如果现金金额大于所购车票金额，自动售票机会计算现金金额与所购车票金额的差值，然后开始找零。自动售票机找零过程使用的就是贪心算法，它会先使用自动售票机内存储的面值最大的硬币，再依次选用面值次之的硬币，直至符合找零的钱数，最后通过出币口将零钱找给购票者。自动售票机的找零过程既然是用的贪心算法。同学们可能就要问了，自动售票机是如何用贪心算法来找零的呢？在找零过程中我们会通过眼睛来发现面值最大的硬币，然后对硬币进行组合。计算机是如何发现面值最大的硬币呢？它又是怎么来组合硬币的呢？要揭开这些谜团，这就需要我们来进一步了解算法。自动售票机的找零过程实际就是模仿人来找零的过程，这应该涉及到AI了，也就是人工智能，在这里我们不谈AI，要谈也是以后谈，当我们具备更多的知识后再谈。自动售票机没有眼睛，它不能像人一样直接去识别硬币的面值。但人类是聪明的，人类可以把不同面值的硬币放置到自动售票机的不同硬币盒中，每个硬币盒都放置相同面值的硬币，这些硬币盒放置的硬币构成了贪心算法的输入。贪心算法会知道每个硬币盒放置的面值大小，这都是在算法中安排好的。当它开始找零时，它会先从存有最大面值的硬币盒中取出硬币，在取硬币之前，它会先计算需要多少个面值最大的硬币，计算过程也都是在算法中安排好的。这个取硬币的过程和人在找零过程中的行为是一样的。当找零的硬币都准备好后，它会启动输出装置，把取出的硬币通过输出装置输出到取硬币口，人们通过取硬币口就可以取到找零的硬币了。从自动售票机的找零过程，我们可以看到：算法需要有输入、计算过程、还要有输出。在自动售票机的找零算法中，算法的输入就是放置在硬币盒中的硬币面值和硬币数量。计算过程就是根据找零的钱数来计算需要从不同硬币盒中取出硬币的数量，这个计算过程会分成多个步骤，依次从最大面值到最小面值的硬币盒中取出硬币。算法的输出就是把取出的硬币通过自动售票机的输出装置输出到取硬币口。现在我们已经了解了自动售票机找零算法的输入、计算步骤和输出。下一步就是要把算法写成程序输入到自动售票机设备中，让自动售票机设备来执行找零程序。如何将算法编写为程序，我们将在下节课介绍，不过介绍的内容不是自动售票机的找零算法，这个太复杂了，我们还是选择一个比较简单的算法案例，来介绍如何将算法编写为程序。那么，算法与程序是什么关系呢？算法与程序的关系是相互依附的关系，算法要在计算机或类似自动售票机设备上执行，就必须将算法的步骤用编程语言描述出来，编译通过后，方可在计算机上执行。用编程语言描述算法的过程就是编写程序，编写的程序编译通过后，就是可以在计算机上执行的程序了。下面我们来对算法做个小结：（1）算法要有输入算法是用来解决问题的，问题中的数据就是算法的输入。例如贪心算法在找零问题的中输入是要找的零钱数、硬币面值以及硬币的数量。假如张某现在有1元的硬币2个、5角的硬币3个、1角的硬币6个，张某使用贪心算法找零1.8元。贪心算法的输入就是2个1元的硬币、3个5角的硬币和6个1角的硬币、以及1.8元要找的零钱数。（2）算法的步骤是有限的算法在解决问题的过程中，可以分成多个步骤来执行。例如，用贪心算法找零的第一步就是先用面值最大的硬币，当面值最大的硬币组合不能满足找的零钱数时；就要执行第二步再选用面值次之的硬币，如果还不能满足找的零钱数；就要执行第三步再选用面值更小的硬币，如果还不满足找零要求；就要执行第四步……；直至满足找零要求或者找不开零钱。不管问题是否能够解决，算法最终会在有限的步骤内结束。（3）算法要有结果算法既然是要解决问题的，算法执行完成后，就要有解决问题的结果。不管是解决成功还是解决失败，算法都要给出结果。例如，在使用贪心算法解决找零问题中，算法给出的结果或者是找零成功，或者是找零失败。课后小练习同学们应该知道如何计算长方形的面积吧。如果让计算机来计算长方形的面积，计算长方形面积的算法步骤有哪些呢？要求使用文字来描述计算长方形面积算法的步骤。提示：算法的步骤有输入、计算过程和输出。
转载请注明：http://www.aierlanlan.com/rzdk/8814.html
