cpp1.cpp

正整数划分算法

#include<iostream.h>
int q(int n,int m)//(表示值为n,划分中的各个数不大于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);
}
void p(int **a,int n,int m,int i,int j)//a[i][j]用于记录第i种划分中的第j+1个数的数值
{
	if((n>m)&&(m>1))
	{
		for(int k=0;k<q(n-m,m);k++)
		{
			a[i+k][j]=m;
		}
		j++;
		p(a,n-m,m,i,j);
		i=i+k;
		p(a,n,m-1,i,--j);
		return;
	}
	if((m==n)&&(n>1))
	{
		a[i][j]=m;
		i++;
		p(a,n,n-1,i,j);
		return;

	}
	if((m>n)&&(n>=1)) 
	{
		p(a,n,n,i,j);
		return;
	}
	if((n>=1)&&(m=1))
	{
		for(int h=0;h<n;h++)
		{
			a[i][j+h]=1;
		}
	}
}
void main()
{
	int n;
	cout<<"请输入想要划分的正整数 ";
	cin>>n;
    int h,k;
	int qn=q(n,n);
	h=0;k=0;
	int **a=new int*[qn];
	for(int j=0;j<qn;j++)
	{
		a[j]=new int[qn];
	};
	for(int i=0;i<qn;i++)
		for(j=0;j<qn;j++)
			a[i][j]=0;
	p(a,n,n,h,k);
	cout<<"共有"<<qn<<"种划分:"<<endl;
	for(i=0;i<qn;i++)
	{
		cout<<a[i][0];
		for(j=1;j<qn;j++)
		{
			if(a[i][j]!=0)
				cout<<"+"<<a[i][j];
		}
		cout<<endl;
	}
}