


下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实训案例名称:用算法实现最少硬币找零问题1.案例描述用JavaScript算法实现最少硬币找零问题。给定要找零的钱数,以及可用的硬币面额d1…dn及其数量,找到所需的最少的硬币个数。例如,有以下面额硬币(美分):d1=1,d2=5,d3=10,d4=25。如果要找36美分的零钱,则可以用1个25美分、1个10美分和1个1美分。2.实现思路最少硬币找零的解决方案是找到n所需的最少硬币数。要实现这一点,首先得找到对每个x<n的解。然后,将解建立在更小的值的解的基础上。3.实现代码functionMinCoinChange(coins){varcoins=coins;//{1}varcache={};//{2}this.makeChange=function(amount){varme=this;if(!amount){//{3}return[];}if(cache[amount]){//{4}returncache[amount];}varmin=[],newMin,newAmount;for(vari=0;i<coins.length;i++){//{5}varcoin=coins[i];newAmount=amount-coin;//{6}if(newAmount>=0){newMin=me.makeChange(newAmount);//{7}}if(newAmount>=0&&//{8}(newMin.length<min.length||!min.length)//{9}&&(newMin.length||!newAmount))//{10}{min=[coin].concat(newMin);//{11}console.log('newMin'+min+'for'+amount);}}return(cache[amount]=min);//{12}};}创建MinCoinChange类接收coins参数(行{1}),代表问题中的面额。可以根据需要传递任何面额。这里为了更加高效且不重复计算值,在行{2}中使用了cache。创建makeChange方法,这是一个递归函数,用于具体实现找零问题。传入参数amount,若amount不为正数,就返回空数组({行3});方法执行介绍后,会返回一个数组,包含用来找零的各个面额的硬币数量(最少硬币数)。接着,检查cache缓存,若结果已经缓存({行4}),则直接返回结果;否则,执行递归算法。基于传入的coins参数(面额基准值)实现找零问题。行{5}中循环coins数组,行{6}对每个面额计算newAmount的值,这个值会一直减小,直到能找零的最小钱数。行{7}若newAmount为正值,则继续计算它的找零结果。最后判断newAmount是否有效以及newMin是否是最优解。返回最终找零结果。运用下面的脚本9-12测试这个算法的找零结果。脚本9-12.html<!DOCTYPEhtml><html><head><title>最少硬币找零问题</title></head><body></body></html><scripttype="text/javascript">functionMinCoinChange(coins){varcoins=coins;//{1}varcache={};//{2}this.makeChange=function(amount){varme=this;if(!amount){//{3}return[];}if(cache[amount]){//{4}returncache[amount];}varmin=[],newMin,newAmount;for(vari=0;i<coins.length;i++){//{5}varcoin=coins[i];newAmount=amount-coin;//{6}if(newAmount>=0){newMin=me.makeChange(newAmount);//{7}}if(newAmount>=0&&//{8}(newMin.length<min.length||!min.length)//{9}&&(newMin.length||!newAmount))//{10}{min=[coin].concat(newMin);//{11}console.log('newMin'+min+'for'+amount);}}return(cache[amount]=min);//{12
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2025学年江西省赣州市定南中学高二(下)期末数学试卷(含答案)
- 2025年百科常识竞赛题库小学
- 2025年网红考试题目及答案
- 2025年茶道考试题库及答案
- 2025年大学建材考试题及答案
- 2025年红岩的测试题2及答案
- 2025年学生楷书考试题及答案
- 2025年大骨节病竞赛题库
- 2025年结构面试题目解析及答案
- 2025医院医疗机构皮肤科年度工作总结报告
- 数学三年级下册暑假练习题(口算,竖式,脱式和应用题)
- 文本信息加工和表达
- ks-s3002sr2腔全自动清洗机规格书megpie
- 厂房改造工程施工组织设计
- 2023年锦州师范高等专科学校高职单招(语文)试题库含答案解析
- 《阿里巴巴“合伙人制度”的是与非》
- 历年托福词汇题汇总440题有答案
- 湘少版英语六年级下册全册教案
- 武汉城市介绍动态模板课件
- 小升初语文文言文阅读真题50题(含答案)
- 燃气行业培训题库燃气燃烧器具安装、维修员(题库)附答案
评论
0/150
提交评论