学步园

《Cracking the coding interview》第八章第七题

有无限数量的25分，10分，5分，1分，写代码计算表示N分的表示方法有多少种。

如N=5；有{5}， {1,1,1,1,1} 两种

int makeChange(int n,int denom){
	int next=0;
	switch(denom){
	case 25:
		next=10;
		break;
	case 10:
		next=5;
		break;
	case 5:
		next=1;
		break;
	case 1:
		return 1;
	}
	int ways=0;
	for(int i=0;i*denom<=n;i++){
		ways+=makeChange(n-i*denom,next);
	}
	return ways;
}

int main(){
	int n;
	cin>>n;
	while(n){
		cout<<"ways:"<<makeChange(n,25)<<endl;
		cin>>n;
	}
	return 0;
}

 ===============2013-6-20==============

如果种类很多应当以数组表示，一个很明显的事实是，当n=0时，应当停止继续递归操作；而上述算法没有如此做，稍微改进后如下：

int change[4]={1,5,10,25};
int makeChange2(int n,int denom){
	if(denom==0 || n==0){
		return 1;
	}
	int ways=0;
	for(int i=0;i*change[denom]<=n;i++){
		ways+=makeChange2(n-i*change[denom],denom-1);
	}
	return ways;
}

int main(){
	int n;
	cin>>n;
	while(n){
		cout<<"ways2:"<<makeChange2(n,sizeof(change)/sizeof(int)-1)<<endl;
		cin>>n;
	}
	return 0;
}

2013.10.11

给定一个整数n，输出所有和为n的自然数 。例如n=3 ，输出 1+1+1， 1+2， 3  三种序列

方法1 ：枚举所有情况(树)，空间复杂度是O(n)

#define MAX 10000
int C[MAX]={0};
int C_i=0;
void f2(int n){
	if(n<=0){
		for(int j=0;j<C_i;j++)
			cout<<C[j]<<" ";
		cout<<endl;
		return;
	}
	for(int i=n;i>0;i--){
		if(C_i>0 && i>C[C_i-1])
			continue;
		C[C_i++]=i;
		if(n-i>=0)
			f2(n-i);
		C_i--;
	}
}

void main(){
	int n;
	while(cin>>n){
	 f2(n);
	}
}