/*
* 正整数划分问题：
* 将正整数n表示成一系列正整数之和，n = n1 + n2 +……+ nk (n1 >= n2 >=……>= nk >= 1, k >= 1)
* 正整数n的这种表示称为正整数n的划分。
* 求正整数n的不同划分数pn。
* Input: n (End with 0)
* Ouput: pn (in each line)
*/
1
// Sulotion 1st:
2#include<iostream>
3using namespace std;
4
5int Count(int n, int m)
6
{
7
if(m == 1) return 1;
8 if(n < m) return Count(n, n);
9 if(n == m) return 1 + Count(n, m - 1);
10 if(n > m) return Count(n - m, m) + Count(n, m - 1);
11
}
12
13int main()
14{
15 int n;
16 cin >> n;
17 while(n != 0)
18
{
19 cout << Count(n, n) << endl;
20 cin >> n;
21
}
22
23 return 0;
24}
1// Solution 2nd:
2#include<iostream>
3using namespace std;
4
5#define MAXN 100
6
7int main()
8{
9 int n, a[MAXN][MAXN], max, i, j;
10
11 // 初始值
12 a[1][1] = 1;
13 max = 1;
14
15 cin >> n;
16 while(n != 0)
17 {
18 if(n > max)
19 {
20 for(i = max + 1; i <= n; i++)
21 {
22 a[i][1] = a[i - 1][1];
23 for(j = 2; j <= i / 2; j++)
24 a[i][j] = a[i - j][j] + a[i][j - 1];
25 for(; j <= i - 1; j++)
26 a[i][j] = a[i - j][i - j] + a[i][j - 1];
27 a[i][j] = 1 + a[i][j - 1];
28 }
29 max = n;
30 }
31 cout << a[n][n] << endl;
32 cin >> n;
33 }
34 return 0;
35}