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
// 查看本栏目更多精彩内容：http://www.bianceng.cnhttp://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]);  

})();

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索return
， array
， solve
， var
， length
， arr
， ret
i和i
美元硬币面值对照图、日本硬币面值、美国硬币的面值和图案、美元硬币面值、欧元硬币面值，以便于您获取更多的相关知识。