NOIP2001 提高组 - 数的划分：算法与实现/n/n## 题目描述/n/n将整数 'n' 分成 'k' 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。/n/n例如：'n=7'，'k=3'，下面三种分法被认为是相同的。/n/n'1,1,5'; /n'1,5,1'; /n'5,1,1'./n/n问有多少种不同的分法。/n/n## 输入格式/n/n'n,k' ('6<n /le 200'，'2 /le k /le 6')/n/n## 输出格式/n/n'1' 个整数，即不同的分法。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n7 3/n/n/n### 样例输出 #1/n/n/n4/n/n/n## 提示/n/n四种分法为： /n'1,1,5'; /n'1,2,4'; /n'1,3,3'; /n'2,2,3'./n/n**【题目来源】**/n/nNOIP 2001 提高组第二题/n/n## 算法思路/n/n可以使用深度优先搜索 (DFS) 来解决这个问题。DFS 的基本思想是：/n/n1. 递归： 从 'n' 开始，枚举每一份的大小 'i' (1 <= i <= n)。/n2. 减枝： 为了避免重复，保证 'i' 不大于上一份的大小。/n3. 终止条件： 当 'k' 份都划分完毕时，判断 'n' 是否为 0，如果为 0，则找到一种有效方案。/n/n## C++ 代码实现/n/ncpp/n#include <iostream>/nusing namespace std;/n/nint count = 0;/n/nvoid divide(int n, int k, int last) {/n if (k == 0) {/n if (n == 0) {/n count++;/n }/n return;/n }/n for (int i = 1; i <= n; i++) {/n if (i <= last) {/n divide(n - i, k - 1, i);/n }/n }/n}/n/nint main() {/n int n, k;/n cin >> n >> k;/n divide(n, k, n);/n cout << count << endl;/n return 0;/n}/n/n/n## 代码解释/n/n1. count: 全局变量，用来记录不同的分法总数。/n2. divide(n, k, last): 递归函数，'n' 表示剩余要划分的数字，'k' 表示剩余要分的份数，'last' 表示上一份的大小。/n3. 递归终止条件： 当 'k' 等于 0 时，判断 'n' 是否为 0，如果是，则表示找到了一个有效的方案，将 'count' 加 1。/n4. 循环遍历： 循环枚举每一份的大小 'i'，并递归调用 divide() 函数。/n5. 减枝： 使用 'last' 参数，保证每一份的大小不超过上一份的大小，从而避免重复方案。/n6. 主函数 main(): 输入 'n' 和 'k'，调用 divide() 函数，并输出 'count' 的值。/n/n## 总结/n/n本题通过 DFS 算法，巧妙地利用递归和减枝技巧，有效地避免了重复计算，最终得到正确的结果。/n/n希望这篇讲解能够帮助您理解这道 NOIP 2001 提高组的经典题目，并在实际应用中运用 DFS 算法解决类似问题。