整数分化问题

整数划分问题

问题描述:将正整数n表示成一系列正整数之和,n=n1+n2+…+nk,其中,n1>n2>…>nk,k>=1。正整数n的不同划分个数为s的划分数,记为p(s)。例如,6和11种不同的划分,所以p(6)=11,分别是:
6;5+1;4+2;4+1+1;3+3;3+2+1;3+1+1+1;2+2+2;
2+2+1+1;2+1+1+1+1;1+1+1+1+1+1。

思路:

整数分化问题_第1张图片

 一般,经过分析,我们解决这个问题会先选定一个较大的标准,剩下的数再进行划分,所以,在确定递归条件时,除了题目规定的值,还要关心解题者自己开始规定的值。
 设p(m,n)为m对n的划分,意义为对m的划分中有一个最大值n,剩余m-n的部分再进行划分。按照这个想法,我们可以发现p(m,1)的划分和p(1,m)的划分有且只有一个,可以作为我们设计递归的递归边界,p(m,1)为1+1+…+1,p(1,m)为1。
p(n,m)=p(n,n-1)+1(m=n):等式右边的1表示n只包含等于n本身,q(n,n-1)表示n的所有其他拆分,即最大零数不超过n-1的拆分。
例:p(6,6)=1+p(6,5)中“1”为“6”,p(6,5)为“5+1,4+2…”
q(n,m)=q(n,m-1)+q(n-m,m):等式右边的q(n,m-1)表示零数中不包含m的拆分式数目,q(n-m,m)表示零数中包含m的拆分数目,因为若确定了一个拆分的零数中包含m,则剩下的部分就是对n-m进行不超过m的拆分。
递归边界:
1.n<1 or m<1 递归返回
2.n=1 or m=1 递归返回
递归条件:
1.n 2.n>m ,返回q(n,m-1)+q(n-m,m)
3.n=m ,返回q(n,m-1)+1

代码如下:

#include
#include
int FH(int n,int m){
     
	if(n<1||m<1)
		return 0;
	if(n==1||m==1)
		return 1;
	if(n<m)
		return FH(n,n);
	if(n==m)
		return FH(n,m-1)+1;
	if(n>m)

		return FH(n,m-1)+FH(n-m,m);
}
void main()
{
     
	int n,s;
	s=0;
	printf("输入n的值:");
	scanf("%d",&n);
	s=FH(n,n);
	printf("%d的划分有%d种划分",n,s);
	system("pause");
}

你可能感兴趣的