JavaScript程序设计基础教程实训指导-9-2 实训案例名称：用算法实现最少硬币找零问题

实训案例名称用算法实现最少硬币找零问题案例描述

1.用算法实现最少硬币找零问题给定要找零的钱数以及可用的硬币面额及其数量，找到JavaScript dl...dn所需的最少的硬币个数例如，有以下面额硬币美分如果要找美分的零钱，则dl=l,d2=5,d3=10,d4=2536o可以用个美分、个美分和个美分12511011实现思路

2.最少硬币找零的解决方案是找到所需的最少硬币数要实现这一点，首先得找到对每个的解然后，n xn将解建立在更小的值的解的基础上实现代码

3.function MinCoinChangecoins{var coins=coins;//{1}var cache={};//{2}口；this.makeChange=functionamount{var me=this;if!amount{//{3}returnifcache[amount]{//{4}return cache[amount];var min=[],newMin,newAmount;forvar i=0;icoins.length;i++{//{5}varcoin=coins[i];newAmount=amount-coin;//{6}ifnewAmount=0{newMin=me.makeChangenewAmount;//{7}}ifnewAmount=0//{8}newMin.Iengthmin.length||!min.length//{9}newMin.length||InewAmount//{10}{min=[coin].concatnewMin;//{11}；console.logfnew Min+min+for*+amount;return cache[amount]=min;//{12}创建类接收参数行{代表问题中的面额可以根据需要传递任何面额MinCoinChange coins1},这里为了更加高效且不重复计算值，在行中使用了{2}cache创建方法，这是一个递归函数，用于具体实现找零问题传入参数若不为正数，makeChange amount,amount就返回空数组{行；方法执行介绍后，会返回一个数组，包含用来找零的各个面额的硬币数量最少硬币数3}卜接着，检查缓存，若结果已经缓存{行，则直接返回结果；否则，执行递归算法cache4}基于传入的参数面额基准值实现找零问题行中循环数组，行对每个面额计算coins{5}coins{6}newAmount的值，这个值会一直减小，直到能找零的最小钱数行若为正值，则继续计算它的找零结果最{7}new Amount后判断是否有效以及是否是最优解返回最终找零结果newAmount newMin运用下面的脚本测试这个算法的找零结果9-12脚本9-

12.html!DOCTYPE htmlhtmlhead〈最少硬币找零问题〈/〉title,title/headbody/body/htmlscript type=,text/javascript,,function MinCoinChangecoins{var coins=coins;//{1}var cache={};//{2}this.makeChange=functionamount{var me=this;if!amount{//{3}口;return}ifcache[amount]{//{4}return cache[amount];}var min=[],newMin,newAmount;forvar i=0;icoins.length;i++{//{5}var coin=coins[i];newAmount=amount-coin;//{6}ifnewAmount=0{newMin=me.makeChangenewAmount;Z/{7}}ifnewAmount=0Z/{8}newMin.Iengthmin.length||!min.length//{9}newMin.length||InewAmount//{10}min=[coin].concatnewMin;//{11}；console.Iognew Min,+min+for+amount;}return cache[amount]=min;//{12}varminCoinChange=new MinCoinChange[1,3,4];console.logminCoinChange.makeChange6;/script这里当找零数为时，最佳答案是两枚价值为的硬币63。