JavaScript程序设计基础教程实训指导-9-2 实训案例名称:用算法实现最少硬币找零问题_第1页
JavaScript程序设计基础教程实训指导-9-2 实训案例名称:用算法实现最少硬币找零问题_第2页
JavaScript程序设计基础教程实训指导-9-2 实训案例名称:用算法实现最少硬币找零问题_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实训案例名称:用算法实现最少硬币找零问题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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论