肖红德

XIAO Hongde

河南大学 数学与统计学院，河南 开封 475004

School of Mathematics and Statistics,Henan University,Kaifeng,Henan 475004,China

1 概述

计算机作为一种工具，在处理需要大量计算的场合发挥着巨大的作用，在解决需要大量计算的问题上，一般涉及两方面：一方面是需要设计相关的算法尽量降低算法的复杂度；另一方面在通过计算机语言进行实现的时候还需要对算法进行优化，从而使得在解决问题时尽可能地提高效率。本文通过结合埃拉托色尼筛法、迪杰斯特拉算法和图的广度优先遍历算法的思想，提出了一种用来计算平均钱币数量的快速算法，即最少钱币数量筛法，并通过计算给定范围的三种钱币组合计算其平均钱币数量，与动态规划算法相比，计算速度明显加快，与贪心算法相比，计算结果更好。对于给定范围、给定钱币种类，如何确定钱币组合这个问题，本文通过对不同钱币之间数值特征的分析，给出了各个数值满足的拟合曲线，从而在寻找最佳钱币种类组合上使得算法的时间复杂度大大降低，程序的运算时间大大缩短。文中选择MATLAB R2017b作为运行环境，针对上述提出的两种算法进行了具体实现。

2 相关研究

关于纸币面值的组合情况研究，Jeffrey已经给出了相关研究结果，见参考文献[1]。其结果如表1所示。

表2给出的货币最佳发行方案是通过动态规划算法计算出来的。动态规划有关的算法见参考文献[2-4]，本文计算的结果与Jeffrey给出的结果不同，原因是Jeffrey计算的范围包括1但不包括100，且按照100进行平均。如果本文也按照这样的方法进行计算，则得到的结果与Jeffrey相同。……