整数划分问题.cpp

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

#include <iostream.h>

int q (int n, int m, int *p, int length);
void print(int *p, int length);

int main()
{
	const int max = 100;
	int a ;
	int count = 0; 
	int length = 0;
	int p[max] = {0};
	cout<<"请输入数字：";
	cin>>a;
	count = q (a, a, p, length);
	cout <<a<< "的划分方法数是：" << count << endl;
	return 0;
}

int q (int n, int m, int *p, int length)
{
	if(n<1||m<1)
		return 0;
	if(n==1||m==1)
	{
		//n=1
		if(n==1)
		{
			p[length] = n;
			print(p, length+1);
		}
		//m=1
		else
		{
			for(int k=0;k<n;k++)
			{
				p[length++] = m;
			}
			print(p,length);
		}
		return 1;
	}
	if(n==m)
	{
		p[length] = m;
		print(p,length+1);
		
		int temp = q(n,m-1,p,length);
		return 1 + temp;
	}
	if(n<m)
	{
		int temp = q(n,n,p,length);
		return temp;
	}
	//n>m>1
	p[length] = m;
	int temp1 = q(n-m,m,p,length+1);
	int temp2 = q(n,m-1,p,length);
	return  temp1 + temp2;
}

void print(int *p, int length)
{
	 cout<<"...进行整数划分..."<<endl;
	 for (int i=0; i<length-1; i++)
		 cout << p[i] << "+";
	 cout << p[i];
	 cout << endl;
}