总时间限制: 100ms 内存限制: 65536kB
描述
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。
输入
标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。
输出
对于每组测试数据，输出N的划分数。
样例输入
5
样例输出
7
提示
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
注意对比题目：
（1）数的划分（把n分为k份，有点类似于放苹果，但放苹果这道题目里面盘子可以为空，它不允许为空。）
（2）复杂的整数划分
算法（一）递归法
把一个正整数n写成如下形式： n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,...,mi}为n的一个划分。如果{m1,m2,...,mi}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
例如当n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};注意4=1+3 和 4=3+1被认为是同一个划分。
根据n和m的关系，考虑以下几种情况：
(1)当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};
(2) 当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,...,1};
(3) 当n=m时，根据划分中是否包含n，可以分为两种情况：
(a). 划分中包含n的情况，只有一个即{n}；
(b). 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。因此 f(n,n) =1 + f(n,n-1);
(4) 当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);
(5) 但n>m时，根据划分中是否包含最大值m，可以分为两种情况：
(a). 划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m, m);
(b). 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);因此 f(n, m) = f(n-m, m)+f(n,m-1);
综合以上情况，我们可以看出，上面的结论具有递归定义特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，将会转换为情况（5）。而情况（5）为通用情况，属于递推的方法，其本质主要是通过减小m以达到回归条件，从而解决问题。其递推表达式如下：
f(n, m) =1; (n=1 or m=1)
=f(n, n); (n<m)
=1+ f(n, m-1); (n=m)
=f(n-m,m)+f(n,m-1); (n>m)
1 #include <stdio.h> 2 long long GetPartitionCount(int n,int max) 3 { 4 if(n==1||max==1) return 1; 5 else if(n<max) return GetPartitionCount(n,n); 6 else if(n==max) return 1+GetPartitionCount(n,max-1); 7 else return GetPartitionCount(n,max-1)+GetPartitionCount(n-max,max); 8 } 9 int main(int argc, char *argv[]) 10 { 11 int n; 12 while(scanf("%d",&n)!=EOF) 13 { 14 printf("%lld\n",GetPartitionCount(n,n)); 15 } 16 return 0; 17 }
算法（二）动态规划
这道题就是整数的划分，其实定义好了状态，就是简单的动态规划的递推。
我们定义dp[n][k]表示将n进行划分，最大的数不超过k的方案有多少种，那么我们可以得到如下的递推方案：
dp[n][k] = dp[n][k-1] + dp[n-k][k];
其中的dp[n][k-1]便是将n进行进行整数的划分，最大的数不超过k-1的方案数；dp[n-k][k]表示拿出一个k后，剩下的数被不超过k的数的表示的方案数。
其中当k>n的时候，则和dp[n][n]的值相同，下面通过递推的方式求出所有的解，然后对应的输入n，输出dp[n][n]就行了。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 using namespace std; 6 7 const int MAX = 122; 8 int dp[MAX][MAX]; 9 10 void Dynamic() 11 { 12 for(int i=1; i<MAX; i++) 13 { 14 dp[i][1] = dp[1][i] = dp[0][i] = 1; 15 } 16 for(int i=2; i<MAX; i++) 17 { 18 for(int j=2; j<MAX; j++) 19 { 20 if(j<=i) dp[i][j] = dp[i][j-1] + dp[i-j][j]; 21 else dp[i][j] = dp[i][i]; 22 } 23 } 24 } 25 int main() 26 { 27 int n; 28 Dynamic(); 29 while(scanf("%d",&n)!=EOF) 30 { 31 printf("%d\n",dp[n][n]); 32 } 33 return 0; 34 }
这道题的动规思路，下面的论述比较清晰一些：
整数划分问题
数 n 的划分是将 n 表示成多个正整数之和的形式，划分可以分为两种情况：
第一种情况：划分的多个正整数中，正整数的数量是任意的。
这又可以分为划分的正整数中，正整数可以相同与不同两类
1. 划分的多个正整数可以相同, 递推方程可以表示为：
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m]
分析dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。则划分数可以分为以下两种情况:
a. 划分中每个数都小于 m， 相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].
b. 划分中有至少一个数为 m. 那就在 n中减去 m , 剩下的就相当于把 n-m 进行划分， 故划分数为 dp[n-m][m];
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
其中dp[n][m]表示整数 n 的划分中，每个数不小于 m 的划分数。同理可证明该式。
2. 划分的多个正整数互不相同，递推方程可以表示为：
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
分析： dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。同样划分情况分为以下两种情况：
a. 划分中每个数都小于 m, 相当于每个数不大于 m- 1,划分数为 dp[n][m-1].
b. 划分中有一个数为 m. 在 n 中减去 m, 剩下相当对n- m 进行划分，并且每一个数不大于 m- 1，故划分数为 dp[n-m][m-1]
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
其中dp[n][m]表示整数 n 的划分中，每个数不小于 m 的划分数。
第二种情况：划分的多个正整数中，正整数的数量是固定的
把一个整数 n 无序划分成 k 份互不相同的正整数之和的方法总数。 方程为： dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
证明方法参考： http://www.mydrs.org/program/html/0369.htm
另一种理解，总方法可以分为两类：
第一类: n 份中不包含 1 的分法，为保证每份都 >= 2，可以先拿出 k 个 1 分
到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
第二类: n 份中至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩
下的 n- 1 再分成 k- 1 份即可，分法有：dp[n-1][k-1]
类似问题：
M个小球装N个盒子，或者苹果装盘问题。比如：把M个球放到N个盒子,允许有空的盒子(不放球),有多少种放法?这些都属于典型的DP问题。
用F(m,n)表示有多少种放法:
如果m=0 或者 m=1 , F = 1
如果n=0 或者 n=1 , F =1
既F(0,0) = F(0,1) = F(1,0) = F(1,1) = 1
否则 F = F(m-n,n) + F(m,n-1)这就是DP的解空间递归解
关于整数的质因子和分解
【问题描述】
歌德巴赫猜想说任何一个不小于6的偶数都可以分解为两个奇素数之和。对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。对于一个给定的整数，输出所有这种素数和分解式。注意，对于同构的分解只输出一次（比如5只有一个分解2 + 3，而3 + 2是2 + 3的同构分解式）。
例如，对于整数8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5
【算法分析】
由于要将指定整数N分解为素数之和，则首先需要计算出该整数N内的所有素数，然后递归求解所有素数和分解即可。
原作者的C++代码：（感觉其实就是回溯的思路）
1 #include <iostream> 2 #include <vector> 3 #include <iterator> 4 #include <cmath> 5 using namespace std; 6 7 // 计算num内的所有素数（不包括num） 8 void CalcPrimes(int num, vector<int> &primes) 9 { 10 primes.clear(); 11 if (num <= 2) 12 return; 13 14 primes.push_back(2); 15 for (int i = 3; i < num; i += 2) 16 { 17 int root = int(sqrt(i)); 18 int j = 2; 19 for (j = 2; j <= root; ++j) 20 { 21 if (i % j == 0) 22 break; 23 } 24 if (j > root) 25 primes.push_back(i); 26 } 27 } 28 29 // 输出所有素数组合(递归实现) 30 int PrintCombinations(int num, const vector<int> &primes, int from, vector<int> &numbers) 31 { 32 if (num == 0) 33 { 34 cout << "Found: "; 35 copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " ")); 36 cout << '\n'; 37 return 1; 38 } 39 40 int count = 0; 41 42 // 从第from个素数搜索，从而避免输出同构的多个组合 43 int primesNum = primes.size(); 44 for (int i = from; i < primesNum; ++i) 45 { 46 if (num < primes[i]) 47 break; 48 numbers.push_back(primes[i]); 49 count += PrintCombinations(num - primes[i], primes, i, numbers); 50 numbers.pop_back(); 51 } 52 53 return count; 54 } 55 56 // 计算num的所有素数和分解 57 int ExpandedGoldbach(int num) 58 { 59 if (num <= 3) 60 return 0; 61 62 vector<int> primes; 63 CalcPrimes(num, primes); 64 65 vector<int> numbers; 66 return PrintCombinations(num, primes, 0, numbers); 67 } 68 69 int main() 70 { 71 for (int i = 1; i <= 20; ++i) 72 { 73 cout << "When i = " << i << ":\n"; 74 int count = ExpandedGoldbach(i); 75 cout << "Total: " << count << "\n\n"; 76 } 77 }
C语言代码如下：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 5 #define maxNum 1000 6 int primeNum[maxNum]={0},ansArr[maxNum]={0}; 7 int indexForPrimeNum,indexForAnsArr; 8 9 int work(int num);//输出num的所有素数和分解的方案并返回其总方案数 10 int CalcPrimes(int num);//计算num内的所有素数（不包括num），结果保存在primeNum[]. 11 12 int PrintAns(int num,int from); 13 //回溯法的思想：从primeNum[]的第from个元素开始选择元素来累加构造num。 14 //构造结果放在ansArr[]中。寻找到一个构造方案后输出该方案. 15 //最终返回总的方案数 16 17 int main(int argc, char *argv[]) 18 { 19 for (int i = 1; i <= 20; ++i) 20 { 21 printf("When i = %d:\n",i); 22 int count = work(i); 23 printf("Total: %d\n\n",count); 24 } 25 return 0; 26 } 27 //计算num内的所有素数（不包括num），结果保存在primeNum[]. 返回数组元素个数 28 int CalcPrimes(int num) 29 { 30 int i,j,root,k=0; 31 32 if(num<2) return k; 33 memset(primeNum,0,sizeof(primeNum)); 34 35 primeNum[k++]=2; 36 for(i=3;i<num;i++) 37 { 38 root=sqrt(i); 39 for(j=2;j<=root;j++) 40 { 41 if(i%j==0) break; 42 } 43 if(j>root) primeNum[k++]=i; 44 } 45 return k; 46 } 47 //调用PrintAns()输出num的所有素数和分解的方案，返回其总方案数 48 int work(int num) 49 { 50 if(num<=3) return 0; 51 52 indexForPrimeNum=CalcPrimes(num); 53 54 memset(ansArr,0,sizeof(ansArr)); 55 indexForAnsArr=0; 56 return PrintAns(num,0); 57 } 58 59 //回溯法的思想：从primeNum[]的第from个元素开始选择元素来累加构造num。 60 //构造结果放在ansArr[]中。寻找到一个构造方案后输出该方案. 61 //最终返回总的方案数 62 int PrintAns(int num,int from) 63 { 64 int i; 65 if(num==0) 66 { 67 printf("Found: "); 68 for(i=0;i<indexForAnsArr;i++) printf(" %d",ansArr[i]); 69 printf("\n"); 70 return 1; 71 } 72 73 int totalCount = 0; 74 //从第from个素数搜索，从而避免输出同构的多个组合 75 for(i=from;i<indexForPrimeNum;i++) 76 { 77 if(num<primeNum[i]) break; 78 ansArr[indexForAnsArr++]=primeNum[i]; 79 totalCount+=PrintAns(num-primeNum[i],i); 80 indexForAnsArr--; 81 } 82 return totalCount; 83 }
参考：
http://www.cppblog.com/superKiki/archive/2010/05/27/116506.html
http://blog.csdn.net/geniusluzh/article/details/8118683
