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

Javascript实现硬币面值的组成和排列2014-09-23问题描述：

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 // 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]）;}）（）;