问题描述
将正整数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。
假设: 将最大加数n1不大于m的划分个数记作q(n,m)
分析:
有如下几种情况:
-
q(n,1) n≥1;
当最大数n1不大于1时,任何正整数n只有一种划分形式: n=1+1+…+1(共n个)
-
q(n,m) m≥n
q(n,n);最大加数n1实际上不能大于n。因此,q(1,m)=1。
-
q(n,n)
1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。
-
q(n,m) n>m>1
q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1 的划分组成。
可得关系式:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2csQzaU1UMBR1T3FleYhnRzwEMW1mY1RzRapnTtxkb5ckYplTeMZTTINGMShUYfRHelRHLwEzX39GZhh2css2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xyayFWbyVGdhd3LcV2Zh1Wa9M3clN2byBXLzN3btg3Pn5GcuAjN3UDO1EjM4ADMxkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
C++代码如下:
#include<iostream>
using namespace std;
int f(int n,int m){
if(n<1)
return 0;
else if(n==1||m==1)
return 1;
else if(n<m) return f(n,n);
else if(n==m) return f(n,m-1)+1;
return f(n,m-1)+f(n-m,m);
}
int main(){
int n;
n=f(6,4);
cout<<n<<" "; return 0;
}