整数划分.c

算法分析ACM题目：整数划分算法 保证能运行！算法分析课程必备！

#include<stdio.h>


int q(int n,int m)
{
	if((n<1)||(m<1))
		return 0;
	if((n==1)||(m==1))
		return 1;
	if(n<m)
		return q(n,n);
	if(n==m)
		return q(n,m-1)+1;
	return q(n,m-1)+q(n-m,m);
}

int q_ji(int n,int m)
{
	if((n<1)||(m<1))
		return 0;
	if((n==1)||(m==1))
		return 1;
	if(n<m)
		return q_ji(n,n);
	if(n==m)
	{
		if(m%2==0)
			return q_ji(n,m-1);
		else
			return 1+q_ji(n,m-1);
	}
	else 
	{
		if(m%2==0)
			return q_ji(n,m-1);
		else
			return q_ji(n,m-1)+q_ji(n-m,m);
	}
}
int q_bu(int n,int m)
{
	if(n==1)
		return 1;
	else if(m==1)
		return  0;
	if(n<m)
		return q_bu(n,n);
	if(n==m)
		return q_bu(n,m-1)+1;
	return q_bu(n,m-1)+q_bu(n-m,m-1);
}

main()
{
	int j,k;
	scanf("%d",&j);
	scanf("%d",&k);
	printf("%d\n",q(j,j));
	printf("%d\n",q(j,k));
	printf("%d\n",q_ji(j,j));
	printf("%d\n",q_bu(j,j));
}