找零问题

我们一起讨论一个生活中常见的问题，找零钱问题。现在假设有面值1角、2角、5角、10角（1元）的硬币各10枚，要求用最少的硬币数量来找零。

例如：找1.3元的零钱，1.3元转换成角，就是13角。

找零钱就是把不同面值或同一面值的硬币组合起来，组合的面值等于需要找零的钱数。1.3元就是13角。

图中A、B、C三种硬币的组合方法：

A组合方法：1个10角的硬币、3个1角的硬币;

B组合方法：1个10角的硬币、1个2角的硬币、1个1角的1币；

C组合方法：2个5角硬币、1个2角硬币、1个1角硬币。

找零问题的最优解

前面的找零问题中，B组合是最优解，用的硬币数量最少，其实在找零问题上，我们一直在使用一种算法，这种算法就是贪心算法。

对比A、B、C三种组合，我们发现B组合在找零过程中，它首先选用面值最大的10角硬币1枚，由于5角硬币不满足组合要求（找零过程中硬币的组合面值不能大于找零的零钱数），它继续选用比5角硬币面值次之的2角硬币1枚（找零过程中硬币的组合面值不能大于找零的零钱数），最后选用比2角硬币面值次之的1角硬币1枚。

前面我们讨论的A、B、C三种找零组合，是在已经预知硬币面值和硬币数量的前提下，给出的找零1.3元的解决方法，解决方法也可以称为算法，硬币面值的组合过程也就是算法的过程。在找零问题中，我们可以把找零的解决方法称为找零算法。

自动售票机

不知道同学们做过火车或地铁没有，现在火车站或地铁车站都有自动售票机，把购票的纸币输入到自动售票机，自动售票机会根据购票金额进行找零，下面我们就来探寻一下自动售票机找零的内幕。

使用自动售票机购票，当你买好票要付款时，你可以把现金竖着放入到自动售票机的条形孔中，自动售票机会自动把现金吸取到自动售票机中，现金只能一张一张放入，现金放入完成后。自动售票机会识别你放入的现金金额，如果现金金额不足给出金额不足提示。如果现金金额大于所购车票金额，自动售票机会计算现金金额与所购车票金额的差值，然后开始找零。

自动售票机找零过程使用的就是贪心算法。在自动售票机中，一般会存储1元硬币、5角硬币、1角硬币各若干枚。在找零过程中，它会先使用自动售票机内存储的面值最大的硬币，再依次选用面值次之的硬币，直至符合找零的钱数，最后通过出币口将零钱找给购票者。

从自动售票机的找零过程，我们可以看到：算法需要有输入、计算过程、还要有输出。在自动售票机的找零算法中，算法的输入就是放置在硬币盒中的硬币面值和硬币数量。计算过程就是根据找零的钱数来计算需要从不同硬币盒中取出硬币的数量，这个计算过程会分成多个步骤，依次从最大面值到最小面值的硬币盒中取出硬币。算法的输出就是把取出的硬币通过自动售票机的输出装置输出到取硬币口。

算法的构成

一个完整的算法由输入的数据（如前面的硬币）、有限的执行步骤（算法的执行过程只能是有限的步骤，不能无限制执行下去）和输出结果组成。

算法的输入是算法要处理的数据。例如在自动售票机找零算法中，在硬币盒放置的硬币和要找的零钱数构成了算法的输入。再如在计算从1到10的累加和算法中，数字1、2、3、4、5、6、7、8、9、10构成了算法的输入。

算法在解决问题的过程中，可以分成多个步骤来执行。例如，用贪心算法找零的第一步就是先用面值最大的硬币，当面值最大的硬币组合不能满足找的零钱数时；就要执行第二步再选用面值次之的硬币，如果还不能满足找的零钱数；就要执行第三步再选用面值更小的硬币，如果还不满足找零要求；就要执行第四步 ……；直至满足找零要求或者找不开零钱。不管问题是否能够解决，算法最终会在有限的步骤内结束。

算法既然是要解决问题的，算法执行完成后，就要有解决问题的结果。不管是解决成功还是解决失败，算法都要给出结果。例如，在使用贪心算法解决找零问题中，算法给出的结果或者是找零成功，或者是找零失败。

流程图

在与他人沟通或交流算法时，让他人快速阅读和理解算法是非常重要的，当算法步骤过多或比较复杂时，用文字描述的算法会增加沟通或交流上的困难。

在这种情况下，用图形来描述算法是一种比较好的思路。俗话说：一张图胜过千言万语，用图来描述算法可以让他人快速理解算法的过程和步骤，相对文字来说也引人入胜，与他人进行算法的沟通和交流也非常方便。

因此在描述算法时，除了使用文字描述算法外，还需要学会使用图形来描述算法，并且还要学会阅读他人使用图形描述的算法。人们为了统一算法的图形描述，预定义了一组图形符号，大家都用预定义的图形符号来描述算法，在图形符号上可以加入文字解释，说明该图形符号表示的意义。多个图形符号以及图形符号上的文字解释构成了一张图，这张图称为流程图，用图形符号描述算法的绘制过程也称为绘制流程图。

流程图符号

标准化的流程图有六个图形符号，绘制流程图时也只能使用这六个图形符号。这六个图形符号分别是开始/结束、过程、输入/输出、子过程、判断、流线符号。

算法有开始和结束，在预定义的图形符号中也有“开始/结束”符号。“开始/结束”符号用同一个圆角矩形表示。在绘制流程图时，首先要绘制开始符号，最后绘制结束符号。

算法的每一个步骤（输入和输出步骤、判断步骤除外）都可以使用“过程”符号来表示，矩形内可以添加过程的简要说明。

算法的输入和输出步骤可以使用“输入/输出”符号，“输入/输出”符号用平行四边形来表示。例如从键盘获取用户输入，输出内容到显示器等这些需要输入和输出的步骤，都可以使用“输入/输出”符号来表示。

当一个算法比较复杂时，需要绘制的流程图会非常复杂，在一个页面中不能完全展现。这时，就需要把算法分为多个子算法，分别进行绘制，这就是分而治之的原则，也符合人们解决问题的思路。在整体算法流程图中，用“子过程”符号来表示一个分解后的子算法。

算法中的条件判断步骤可以使用“判断”符号来表示。在条件判断情况下，算法的流程并不是按既定的顺序执行，而是根据不同条件，选择不同的执行路径。

在流程图中，算法的步骤之间用“流线”符号连接，箭头指向表示步骤的流程方向。例如输入步骤（使用输入/输出符号）的下一个步骤是计算步骤（使用过程符号），用“流线”符号连接两个步骤，流线符号的箭尾指向输入步骤，流线符号的箭头指向计算步骤。

如何看流程图

看流程图时，从“开始”符号顺着“流线”符号看算法的每个步骤，遇到“判断”符号（判断步骤），会有两条“流线”符号（连接两个不同步骤），分别查看这两个不同步骤的流程，依次类推。流程图最后的图形符号是“结束”符号。