Javascript实现硬币面值的组成和排列

Javascript实现硬币面值的组成和排列 问描述: In England the currency is made up of pound, , and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, 1 (100p) and 2 (200p). It is possible to make 2 in the following way: 11 + 150p + 220p + 15p + 12p + 31p How many different ways can 2 be made using any number of coins? 实现: 思路: 1.先解决1分，2分，5分的情况 2.递归的思路解决其他情况 (function(){ // prepare Array.prototype.addRange = function(arr){ if(arr == undefined) { return new Array(); } var ret = new Array(); for(var i = 0 ;i < this.length ;i++){ ret.push(this[i]); } for(var i = 0 ;i < arr.length; i++){ ret.push(arr[i]); } return ret; } Array.prototype.constainsArr = function (arr){ var arr1 = new Array(); var isContains = true; for(var i = 0;i < this.length; i++)arr1.push(this[i]); var arr2 = new Array(); for(var i = 0;i < arr.length; i++)arr2.push(arr[i]); var isContain = true; for(var i = 0;i < arr1.length ; i++){ isContain = true; arr1[i] = arr1[i].sort(function(a,b){return a-b;}); arr2 = arr2.sort(function(a,b){return a-b;}); for(var j = 0; j< arr1[i].length; j++) { if(arr1[i][j]!=arr2[j]) isContain = false; } if(isContain) return true; } return false; } // logic // 查看本栏目更多精彩内容:://www.bianceng.cn/webkf/script/ var coins = new Array(1, 2, 5, 10, 20, 50, 100 ,200); var sln = function solve(n){ if(coins.indexOf(n) == -1) throw ex("unexpected coin"); if(n== 1 ) return new Array([1]); if(n == 2) return new Array([1,1],[2]); if(n == 5) return new Array([1,1,1,1,1],[1,1,1,2],[1,2,2],[5]); if(n == 10) { var arr1 = solve(5); var combined= new Array(); for(var i = 0 ;i < arr1.length;i++){ for(var j = 0;j < arr1.length;j++){ var ret = arr1[i].addRange(arr1[j]); if(combined.length == 0 || !combined.constainsArr(ret)){ combined.push(ret); } } } return combined; } if(n == 20){ var arr1 = solve(10); console.log("solved 10 "); console.log(arr1); var combined= new Array(); for(var i = 0 ;i < arr1.length;i++){ for(var j = 0;j < arr1.length;j++){ var ret = arr1[i].addRange(arr1[j]); if(combined.length == 0 || !combined.constainsArr(ret)){ combined.push(ret); } } } return combined; } if(n == 50){ var arr1 = solve(20); var arr2 = solve(10); var combined= new Array(); for(var i = 0 ;i < arr1.length;i++){ for(var j = 0;j < arr1.length;j++){ var ret = arr1[i].addRange(arr1[j]); if(combined.length == 0 || !combined.constainsArr(ret)){ combined.push(ret); } } } var combined2 = new Array(); for(var i = 0 ;i < arr2.length;i++){ for(var j = 0;j < combined.length;j++){ var ret = arr2[i].addRange(combined[j]); if(combined2.length == 0 || !combined2.constainsArr(ret)){ combined2.push(ret); } } } return combined2; } if(n== 100){ var arr1 = solve(50); var combined= new Array(); for(var i = 0 ;i < arr1.length;i++){ for(var j = 0;j < arr1.length;j++){ var ret = arr1[i].addRange(arr1[j]); if(combined.length == 0 || !combined.constainsArr(ret)){ combined.push(ret); } } } return combined; } if(n== 200){ var arr1 = solve(100); var combined= new Array(); for(var i = 0 ;i < arr1.length;i++){ for(var j = 0;j < arr1.length;j++){ var ret = arr1[i].addRange(arr1[j]); if(combined.length == 0 || !combined.constainsArr(ret)){ combined.push(ret); } } } return combined; } } var ret = sln(50); for(var i =0;i < ret.length; i++) console.log(ret[i]); })();