整数划分问题：将正整数n表示成一系列正整数之和：，其中，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}
。
对于任意的正整数
n
，可以表示为一些整数相加的形式，我们可以把
n
的划分函数
p(n)
定义为另一种形式
q(n,m)
。其中，
n
表示那些相加的整数中最大的那一个加数，
m
表示那些相加的整数一定不能够大于
m
。那么对于一个函数
q(n,m)
，我们可以分成
4
种情况来讨论：
情况一：当
n = = 1 || m = = 1
时，返回的是
1
。这里可以分成两个小部分来看，当
n = = 1
时，也就是说最大加数为
1
，自然只有一种情况，当
m = = 1
时，那么相加每一个整数都不能大于
1
，那么也只有全部都是
1
这一种情况。
情况二：当
n = = m
时，返回的是
1+q(n,n-1)
。也就是说
n
的加数就是
n(
因为
n= =m)
，那么这个时候就增加了一种划分情况，就是
n={n}
，但是只是返回
1
是不够的，因为函数
q(n,m)
本身的功能是计算最大加数
n
不大于
m
的划分个数，所以还要进一步递归计算整数
n
不大于
n-1
的划分数，也就是
q(n,m)
。这种情况也是算法第一次被执行就触发的情况，因为算法一开始是求
n
的所有划分情况
,
那么一开始传入的参数为
q(n,n)
，首先第一种情况为
n
的加数是
n
，那么还要继续求
q(n,n-1)
，所以当
n = = m
时，
return 1+q(n,n-1)
。
情况三：当
n < m
时，返回的是
q(n,n)
。我们再一次强调一下
q(n,m)
这个函数的功能时计算最大加数
n
不大于
m
的划分个数，如果
n < m
的时候，这和函数的功能时矛盾的，不过
m
其实可以缩小范围，缩小到
n
，这时只需要计算最大加数
n
不大于
n
的划分个数即可。
情况四：当
n > m > 1
时，返回的是
q(n,m-1) + q(n-m,m)
。在这个条件下，最大加数
n
不能大于
m
，所以最大加数是
m
，那么只需要算最大加数为
n-m
不大于
m
的划分个数就行了，即
q(n-m,m)
，要注意的是条件是不大于
m
，因为当前函数已经说明了最大加数不能够大于
m
了，那么递归的下一层函数也要不大于
m
，比如说：在算
6
的所有划分数时，只能够出现
6=3+2+1
，不能够出现
6=2+3+1
这种情况，因为第一个加数已经确定是
2
的话，第二个加数就一定要小于
2
。
在分析完这
4
中情况之后，给出下面的递归表达式：
为了测试算法的正确性，我们带入题目给出的求正整数
6
划分个数来验证。一开始划分数为
0
。正整数
6
可以由一些加数通过加法相加来得到，为了方便分析，先把这些加数的集合定义为
A
。
第一步：带入
q(6,6)
，进入函数之后，符合
n = = m
这中情况，那么此时首先是增加了第一种情况，就是集合
A
中最大的加数为
6
的时候，只有一种情况，即
6 = {6}
，在划分数加
1
之后，继续递归计算集合
A
中最大加数为
5
的所有划分个数，也就是
q(6,5)
。所以当
n = = m
时，公式：
q(n,m) = 1 + q(n, n-1)
是正确的。
第二步：这一步计算的是
q(6,5)
，符合第四种情况
(n>m>1)
。当集合
A
中最大加数已经确定是
5
之后，那么只需要计算
6-5=1
不大于
5
的所有划分数就是整数
6
的所有以
5
开头的加法因子的划分数，也就是
q(1,5)
。在计算最大加数为
5
的划分数之后，还需要继续递归计算最大加数为
4
的划分数，也就是
q(6,4)
。所以当
n>m>1
时，公式
q(n,m) = q(n,m-1) + q(n-m,m)
是正确的。
第三步：因为上一步有两个递归公式，首先先考虑
q(n-m,m)
也就是
q(1,5)
，当最大加数为
1
的时候，由情况一可以知道只有加数是
1
这一种情况，在这里就可以确定集合
A
中一最大加数为
5
开头的所有划分情况只有一种，就是
6={5+1}
。这里有根据公式
q(n,m) = q(n,m-1) + q(n-m,m)
接着把
q(6,4)
划分为
q(6,3)+q(6-4,2)
。
后面的情况几乎和前面
3
步分析的情况差不多。所以我们可以根据上面的递归公式来计算出任意一个正整数的所有划分数。但是题目还需要打印所有划分的情况，那么我们可以定义一个全局数组变量
int a[]
，来记录每一个加数，所以我们可以把上述所说的递归方程
q(n,m)
改成
q(n,m,i)
，这里的
i
表示数组
a
的下标，那么在每一次递归方法中，第一个操作就是赋值给数组，也就是执行操作
a[i]=m
。
import java.util.Scanner;
public class Lab1_2 {
static int[] a = new int[1000];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while(in.hasNextInt()) {
int n = in.nextInt();
int count = q(n, n, 0);
System.out.println(count);
}
}
public static int q(int n, int m, int i) {
if(n < m) {
return q(n, n, i);
}
a[i] = m;
if(n == 0 || m == 0) {
//打印下标从0到i
printPartition(i);
return 0;
}
if(n == 1 || m == 1) {
if(n == 1) {
//打印下标从0到i
printPartition(i);
}
else q(n-1, 1, i+1);
return 1;
}
if(n == m) {
//打印下标从0到i
printPartition(i);
return 1 + q(n, n-1, i);
}
return q(n-m, m, i+1) + q(n, m-1, i);
}
public static void printPartition(int i) {
System.out.print("{");
for(int j = 0; j <= i; j++) {
if(j == i) System.out.print(a[j]);
else System.out.print(a[j] + "+");
}
System.out.println("}");
}
}