1 / 20
文档名称:

硬币找零.ppt

格式:ppt   大小:280KB   页数:20页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

硬币找零.ppt

上传人:mh900965 2018/2/28 文件大小:280 KB

下载得到文件列表

硬币找零.ppt

文档介绍

文档介绍:硬币找零
题目描述
在现实生活中,我们经常遇到硬币找零的问题,例如,在发工资时,财务人员就需要计算最少的找零硬币数,以便他们能从银行拿回最少的硬币数,并保证能用这些硬币发工资。我们应该注意到,人民币的硬币系统是100,50,29,10,5,2,1,,,,,,,采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。
题目描述
但不幸的是:我们可能没有这样一种好的硬币系统,因此用贪心算法不能求出最少的硬币数,甚至有些金钱总数还不能用这些硬币找零。例如,如果硬币系统是40,30,35元,那么37元就不能用这些硬币找零;95元的最少找零硬币数是3。又如,硬币系统是10,7,5,1元,那么12元用贪心法得到的硬币数为3,而最少硬币数是2。
题目描述
你的任务就是:对于任意的硬币系统和一个金钱数,请你编程求出最少的找零硬币数;如果不能用这些硬币找零,请给出一种找零方法,使剩下的钱最少。
题目描述
【输入格式】
   第1行,为N和T,其中为1≤N≤5000硬币系统中不同硬币数;l≤T≤30000为需要用硬币找零的总数。第2行为N个数值不大于65535的正整数,它们是硬币系统中各硬币的面值。
【输出格式】
     如T能被硬币系统中的硬币找零,请输出最少的找零硬币数。如T不能被硬币系统中的硬币找零,请输出剩下钱数最少的找零方案中的最少硬币数。
思路介绍
对于此题,可以举个例子:
若有1,5,7,10这四种货币,则易知
1=1
2=1+1
3=1+1+1
……
6=5+1
思路介绍
那么推下去可知
表示12这个面值需要的货币数,等于表示11或7或5或2需要的货币数+1。
那么题中若要求表示12所需用的最小货币数,只需寻找表示11或7或5或2需要的货币数中的最小值。
思路介绍
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
1
2
1
2
3
1
2
D[12]min= Min (d[12-1],d[12-5],d[12-7],d[12-10]) +1 =2
面值i
D[i]
最少货币数
思路介绍
那么对于任意的i来说,
d[i]=min(d[i – a] )+1
(a∈{货币面值}且d[i – a] ≠0)
{d[i]=0代表i无法用给定的货币表示}
程序
因此,就得到如下程序:
var
d:array[1..30000]of integer;
{存储表示任意钱数的所需货币最小值}
money:array[1..5000] of integer;
{用于存储各种面值的货币}
i,j,tt,pp,total,moneynum:integer;
{moneynum代表货币种数,total表示要表示的面值}
f:text;
c:integer;

最近更新

2021-2022学年北师大版八年级数学上册期末综合.. 14页

2021年人教版安庆市中考语文模拟试卷及答案 9页

2022-2023学年九年级第一期期中历史试题 11页

2024年童年趣事周记400字 6页

2024年竞选演讲稿(汇总15篇) 26页

2023年材料员之材料员专业管理实务考前冲刺试.. 20页

2024年竞聘申请书范文 29页

2024年竞聘信用社主办会计的演讲稿 4页

2024年竞争 25页

XX理工大学研究生联合培养基地建设项目申报书.. 7页

《宏观经济学》课程教案样例5 37页

「人教部编版」小学六年级上册语文23《月光曲.. 11页

中国人民银行关于试点取消企业银行账户开户许.. 17页

中考科学考前信息必刷卷(宁波专用)(原卷版) 15页

会议接待方案 47页

公路绿化工作策划方案 8页

内蒙古通辽市我是小小石榴籽队会教案 8页

初中思想品德质量检测试题(总) 15页

医院妇科常见疾病分级诊疗指南 29页

历年计算机软考程序设计模拟试题及答案 16页

2024年租房人员租房合同(通用7篇) 8页

2024年秘书部个人工作计划12篇 26页

地质实习心得体会 23页

声乐曲《渔舟唱晚》的创作特色及评析 4页

小升初语文期末真题试卷及答案 1-5套 25页

工程经济学敏感性分析练习题 12页

胰岛素泵的应急预案(1)(1) 6页

2024年家庭助廉倡议书家庭助廉家书(模板篇).. 31页

询价采购公告 8页

农村集体“三资”管理、监督、检查工作自查表.. 8页