整数划分问题的递归算法.cpp

递归和分治法解一系列经典算法

//整数划分问题的递归算法

#include <iostream.h>
int k=0,t[100];

int q(int n,int m)
{
	int x,i;
	if(n<1 || m<1) return 0;
	if(n<m)
	{
		t[k]=n;
		return q(n,n);
	}
	if(n==m)
	{
		cout<<t[0];
		for(i=1;i<=k;i++) cout<<"+"<<t[i];
		cout<<endl;
		return q(n,n-1)+1;
	}
	t[k]=m;
	t[++k]=m;
	x=q(n-m,m);
	t[--k]=m-1;
	x+=q(n,m-1);
	return x;
}

void main()
{
	int n=0;
	cout<<"请输入1个正整数n: ";
	while(n<1) cin>>n;
	t[k]=n;
	cout<<"p("<<n<<")="<<q(n,n)<<endl;
}