同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1909_整数划分问题（分治）

2022-5-16 18:17| 发布者: Hocassian| 查看: 47| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504137829200-Problem List-采集的数据-后羿采集器.html

Pro.ID

1909

Title

整数划分问题（分治）

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1909

AC

485

Submit

851

Ratio

56.99%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

描述

将一个正整数n表示成一系列正整数之和：n = n₁ + n₂ + … + n_k，其中 n₁ ≥ n₂ ≥ … ≥ n_k ≥ 1 ， 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 （ 1 ≤ n ≤ 50 ）

输出

Description

将一个正整数n表示成一系列正整数之和：n = n₁ + n₂ + … + n_k，其中 n₁ ≥ n₂ ≥ … ≥ n_k ≥ 1 ， 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

Input

多行，每行一个正整数 n （ 1 ≤ n ≤ 50 ）

Output

为每个正整数输出一行结果。

Sample Input

6
1

Sample Output

11
1

Hint

“整数划分问题”是一个经典算法问题，解法有多种：分治递归法、动态规划法、类似树的观点、母函数法。

在这里我们提倡采用分治递归的方法来做一下，做出了，再用其他方法做一下。

Author

吴杰豪

样例输入

6
1

样例输出