1
计算机与软件学院
实验报告
2022 – 2023 学年第 1 学期 任课老师:
课程名称
算 法 设 计
与分析
班级
学号
姓名
实验题目
零钱找零问题
实验时间
实验开始日期:2022-11-14
报告提交日期:2022-11-21
实验目的、要求
一、实验题目
贪心法的基本思路是在对问题求解时总是做出在当前看来是最好的选择,也就是说贪心
不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。
人们通常希望找到整体最优解,所以采用贪心法需要证明设计的算法确实是整体最优解
或求解了它要解决的问题。
问题描述:使用贪心算法设计思想设计算法实现找零钱问题。一个小孩买了价值少于 1
美元的糖,并将 1 美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供
了数目不限的面值为 25 美分、10 美分、5 美分、及 1 美分的硬币。售货员分步骤组成要找
的零钱数,每次加入一个硬币。选择硬币时所采用的贪心准则如下:每一次选择应使零钱数
尽量增大。为保证算法的可行性(即:所给的零钱等于要找的零钱数),所选择的硬币不应
使零钱总数超过最终所需的数目。
1)在给定钱币面值的前提下,实现找回尽量少硬币的输出方案
2)分析算法性能
二、实验要求
1.该实验的课内学时是 2 个课时。
2.必须采用 C/C++语言完成。
实验步骤与内容
1、 主要设计思想:
找零问题是典型的贪心问题,但是并不代表所有的找零都能用贪心算法找到最优解。只
有满足贪心选择性质的找零才能找到最优解,本题满足贪心选择性质。首先,计算应当找给
顾客的零钱数,当零钱数大于 25 美分时,在记录 25 美分硬币的数组元素里面加一,同时把
剩余所找的零钱数也减 25 美分。不断重复这个过程,直到剩余所需找的零钱数小于 25 美分
时,如果零钱数大于 10 美分,在记录 10 美分硬币的数组元素里面加一,同时把剩余所找的
钱的总数目也减 10 美分,不断重复这个过程,直到剩余所需找的钱的数目小于 10 美分。5
美分和 1 美分的硬币实现过程同上述过程一样,一直执行到所剩的钱的数目为 0,此时停止
计算,得到最优解。
2、 主要数据结构及其解释:
1.存储硬币面值(coin[4])
2.存储所需相应面值硬币个数(C[4])
3.记录商品价格(price)
4.记录应找零钱数(remain)
3、 模块关系图:(如下图)