硬貨の額面の構成は何種類ありますか?Javascriptが実現します.
3398 ワード
問題の説明:
In England the currency is made up of pound、and pence、p、and there re re eigh coins in general circuulation:
1 p,2 p,5 p,10 p,20 p,50 p,1(100 p)and 2(200 p)
It is possible to make 2 in the follwing way:
1£1+1 50 p+2 20 p+1 5 p+1 2 p+3 1 p
How many different ways can 2 be made using any number of coins?
実装:
考え方:
1.まず1点、2点、5点を解決する場合
2.再帰的な考え方で他の状況を解決する
In England the currency is made up of pound、and pence、p、and there re re eigh coins in general circuulation:
1 p,2 p,5 p,10 p,20 p,50 p,1(100 p)and 2(200 p)
It is possible to make 2 in the follwing way:
1£1+1 50 p+2 20 p+1 5 p+1 2 p+3 1 p
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]);
})();