整数的划分

86 阅读 0 评论 57 点赞

我是靠谱客的博主心灵美耳机，这篇文章主要介绍整数的划分，现在分享给大家，希望可以做个参考。

对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为：

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，一共有11种，其中5+1和1+5被认为是同样的。

输入格式:

输入有多组数据，每行为一个正整数n(n < 50)。

输出格式:

对于每组输入，输出有多少种整数划分的方法。

输入样例:

在这里给出一组输入。例如：

1

6

输出样例:

在这里给出相应的输出。例如：

1
11

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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 q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
int main(){
for(int a;cin >> a;){
cout << q(a,a) << endl;
}
return 0;
}