博客

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。

例如：正整数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。

在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。

#include<iostream>
using namespace std;

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 1 + q(n, m-1);
	}else{
		return q(n, m-1)+q(n-m, m);	
	}
	
}

int main(){
	
	int x = q(6,6);
	cout << x << endl;
}

关键要理解n>m的情况。逐步减少，递归到其他情形中去