找零问题

问题描述：

 

有n美元需找零.

    美元中有x美分,y美分,z美分,a美分,s美分

总共有多少种方式?

分成两步:
    1.计算使用x美分找零的方法数.
    2.上面数目加上除了使用x美分找零的方法数以外的数目.

 

演示@google code

 

代码：

 

想模仿 scheme 很棘手

 

/*
            
            递归解法，金币找零问题,模仿 scheme
            
		a:[{
			value : value ,//当前零钱金额
			index: index  //当前标签
		}]
	*/
function countchange(a, limitW) {
	var option=[];
	var result=[];
	
	function selectcount(i,value) {
		option[i]=value;
		return i;
	}
	
	function unselectcount(i) {
		option[i]--;
	}
	
	function count_iter(i,remain) {
		if(remain == 0) {
			var tmp=[];
			for(var j=0;j<option.length;j++){
				if(option[j]) {
					tmp.push("金额 "+ a[j].value+ " : "+option[j]+" 个 , ");
				}
			}
			result.push(tmp);
			return i;
		}
		if(remain>=a[i].value) {
			//选择 a[i]，计算，然后复原
			unselectcount(
						count_iter(
								selectcount(i,(option[i]||0)+1),remain-a[i].value
											)
										);
		}
		//不选 a[i]
		if(i<a.length-1)
			count_iter(i+1,remain);
		return i;	
	}
	
	count_iter(0,limitW);
	return result;								
}