整数划分问题

1、hoj1402 整数划分zhouguyuehit 【题目描述】整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。每组输入是两个整数n 和 k。 (1 = n = 50, 1 = k = n) 对于每组输入， 请输出六行。第一行：将 n 划分成若干正整数之和的划分数。第二行：将 n 划分成 k 个正整数之和的划分数。第三行：将 n 划分成最大数不超过k 的划分数。第四行：将 n 划分成若干奇正整数之和的划分数。第五行：将 n 划分成若干不同整数之和的划分数。第六行：打印一个空行。【算法分析】本题相当于5 个小问题， 首先来看最容易做的第5 个小问题： 将 n 划分成若干不同

2、整数之和的划分数。 则是一个典型的背包装物品问题，把问题转化一下， 即一个容量为n 的背包，重量分别为1 到 n 的物品各一个，求用若干物品将背包填满的方案总数。利用动态规划的思想，很容易得到方程fi,j = fi-1,j +fi-1,j-i ，其中 fi,j表示从前i 个物品中用若干个组成的总重量为j的方案总数， 转移时要保证fi-1,j-i有意义。答案为 fn,n，时间复杂度为o(n2)。对于前 3 个小问题可以归结为一个问题，即第 2 个小问题： 把将 n 划分成 k 个正整数之和的划分数。为了避免重复， 我们需要按照不下降的顺序进行排列。我们形象地可以把n 的 k 份自然数划分看作n

3、块积木堆成k 列，那么不妨设这n 块积木从左到右被堆成“阶梯状”。比如，下图表示的是3 种 10 的 4 份自然数划分。而将该图旋转90 度，可以很容易想出一种状态表示方法。设 fi,j,k表示把 j划分成 i 份最大为k的划分方案数， 则有 fi,j,k = fi-1,j-k,l ，其中l = 1.k 。时间复杂度为o（n2k2） 。而如果观察第一个图，我们还可以得到一种状态表示方式。设fi,j表示把 i 划分成 j份的划分方案数，则有fi,j = fi-j,k ，其中 k = 0.j 。时间复杂度为o（ nk2） 。又由于 fi,j=fi-j,k （k = 0.j）= fi-j,k（k =

4、 0.j-1 ）+fi-j,j = fi-1,j-1+fi-j,j ，这样就把时间复杂度降为o（nk） 。从另外一个角度想，我们在第一个图中“截去底边”，由于存在一个划分方案中含1 的情况，我们无法确定在“截去底边”之后要把i-j 分为几个数，那么不妨将划分方案中含1 的情况单独列出来讨论，直接得到fi,j = fi-1,j-1+fi-j,j 。对于第 1 个小问题的答案是fn,i（i = 1.n ） ，第 2 个小问题的答案显然是fn,k，而第 3 个小问题的答案则是fn,i（ i = 1.k） ，考虑上面旋转90 度之后的图， 你会发现， fn,i集合中的最高高度均为i，即将 n 划分成最

5、大数为i 的方案数。最后来看第4 个小问题， 就是第 2 个小问题的分奇偶版本，那么设 fi,j表示把 i划分成j个奇数的划分方案数，gi,j 表示把 i 划分成 j个偶数的划分方案数。那么还是用“截去底边”的思想，显然有gi,j = fi-j,j 。但 fi,j却不是直接等于gi-j,j，因为这里又存在一个划分方案中含1 的情况，同样将划分方案中含1 的情况单独列出来讨论，则有fi,j = gi-j,j + fi-1,j-1。最后的答案就是fn,i（i = 1.n） ，时间复杂度为o(n2)。【参考程序】#include #include constint maxn = 51; int n,

6、 k, fmaxnmaxn, gmaxnmaxn; int f1maxnmaxn, f2maxnmaxn; int main () int i, j; int ans1, ans2, ans3, ans4, ans5; f10 0 = 1; for (i = 1; i maxn; i +) for (j = 1; j = i; j +) f1ij = f1i - jj + f1i - 1j - 1; f0 0 = g0 0 = 1; for (i = 1; i maxn; i +) for (j = 1; j = i; j +) gij = fi - jj; fij = fi - 1j - 1

7、 + gi - jj; for (i = 0; i maxn; i +) f2i0 = 1; for (i = 1; i maxn; i +) for (j = 1; j = 0) f2ij += f2i - 1j - i; while ( scanf ( %d %d, &n, &k) != eof ) ans1 = ans2 = ans3 = ans4 = ans5 = 0; for (i = 1; i = n; i +) ans1 += f1ni; ans2 = f1nk; for (i = 1; i = k; i +) ans3 += f1ni; for (i = 1; i =