【问题】将整数n表示为一系列正整数的和。
n = n1 + n2 + ...+ nk (n1 >= n2>=......>=nk>=1,k>=1)
并称之为n的划分。不同的划分个数称为正整数n的划分数，p(n)
建立如下递归关系：
在不同的划分中，将最大的加数n1不大于m的划分数计做q(n,m)
1.q(n,1) = 1,n >= 1;表示，最大加数小于等于1，就是，n1<=1.而n1>=1,因此n1 = 1，该种类型划分只有一种。
2,q(n,m) = q(n,n),m>=n;因此，m >=n > n1. 对于数字m和n他们划分的最大加数，都不会比n大，就说明划分数相同。
3.q(n,n) = 1 + q(n,n-1);n的划分由n1 = n,和n1 <= n-1构成。
4.q(n,m) = q(n,m-1) + q(n-m,m),n > m > 1;
n的最大划分数n1不大于m的划分数（n1 <= m）由，n1 = m和n1 <= m-1构成。
n1 = m,则n2 + n3 + ...+nk = n - m,在对n-m中找到最大为m的划分。表示为q(n-m,m);
n1 <= m - 1,表为q(n,m-1)
扩展：
【输入】标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N)
【输出】
对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目
分析：
分为不同正整数包含：
1.n1 <= m -1 ,q(n,m-1)
2.n1 = m;在从n-m中找到最大为加数为m-1的划分。q(n-m,m-1)
q(n,m) = q(n,m-1) + q(n-m,m-1),分为若干不同数的划分数。
分为K个正整数的划分数：
设置f(n,k)表示为k个数的n的划分。
1.k个数中包含1：其余k-1个数去分n-1的划分。f(n-1,k-1)
2.k个数不包含1：每个数都比1大，k个数都分一个1.其余的n - k在分到k个数中的划分数。f(n - k,k)
f(n,k) = f(n - 1,k-1) + f(n - k,k)
分为若干个奇整数的和：
设置x(i,j),数字i划分为j个奇数的划分数，y(i,j)数字i划分为j个偶数的划分数。
1.包含1：减掉1后，i-1需要分配到j-1个奇数中，x(i-1,j-1)
2.不包含1：对j个奇数都减去1后，就是i-j的j个偶数的划分。y(i-j,j)
x(i,j) = x(i - 1,j-1) + y(i-j,j)
或：
1.m奇数。包含m:q(n -m,m),不包含m，q(n,m-1) ;q(n,m) = q(n -m,m) + q(n,m-1)
2.m偶数。q(n,m) = q(n,m-1)
网友评论