精选优质文档-倾情为你奉上实验三 课程名称：算法设计与实现 实验名称：贪心算法-找零问题 实验日期：2019年5月2日 仪器编号：007 班级：数媒0000班姓名：郝仁 学号 实验内容假设零钱系统的币值是1，p,p2,，pn,p1,且每个钱币的重量都等于1，设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少，说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度。实验分析引理1（离散数学其及应用3.1.4）：若n是正整数，则用25美分、10美分、5美分和1美分等尽可能少的硬币找出的n美分零钱中，至多有2个10美分、至多有1个5美分、至多有4个1美分硬币，而不能有2个10美分和1个5美分硬币。用10美分、5美分和1美分硬币找出的零钱不能超过24美分。证明如果有超过规定数目的各种类型的硬币，就可以用等值的数目更少的硬币来替换。注意，如果有3个10美分硬币，就可以换成1个25美分和1个5美分硬币；如果有2个5美分硬币，就可以换成1个10美分硬币；
