NOIP2001 提高组 - 数的划分：算法解析及 C++ 代码实现

题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;
1,5,1;
5,1,1.

问有多少种不同的分法。

输入格式

n,k （6<n≤200，2≤k≤6）

输出格式

1 个整数，即不同的分法。

样例 #1

样例输入 #1

7 3

样例输出 #1

提示

四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

算法解析

这是一个经典的数学问题，可以使用递归来解决。我们可以将问题分解为两种情况：

第一种情况：将整数 n 划分成 k 份，其中每份至少为 1。我们可以将第一份设为 1，然后将剩下的 n-1 划分成 k-1 份，这样就可以保证每份至少为 1。
第二种情况：将整数 n 划分成 k 份，其中至少有一份为 0。我们可以将其中一份设为 0，然后将剩下的 n 划分成 k 份，这样就可以保证至少有一份为 0。

通过递归的方式，我们可以将问题不断分解为更小的子问题，直到问题变得非常简单。最终，我们可以得到问题的解。

C++ 代码实现

#include <iostream>
using namespace std;

int countPartitions(int n, int k) {
    if (n == 0 || k == 1) {
        return 1;
    }
    if (n < k) {
        return 0;
    }
    return countPartitions(n-1, k-1) + countPartitions(n-k, k);
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << countPartitions(n, k) << endl;
    return 0;
}

代码详解

在上述代码中，我们定义了一个名为 countPartitions 的递归函数。该函数接收两个参数：n 表示要划分的整数，k 表示划分的份数。首先，我们检查基本情况：如果 n 为 0 或 k 为 1，那么只有一种划分方式，即将 n 划分为 k 份（每份都为 0）。如果 n 小于 k，那么无法进行划分，返回 0。否则，我们将问题分解为两种情况，分别递归求解：

将第一份设为 1，然后将剩下的 n-1 划分成 k-1 份。
将其中一份设为 0，然后将剩下的 n 划分成 k 份。

最后，我们将两种情况的结果相加，即可得到问题的解。

在主函数中，我们读取输入的 n 和 k，并调用 countPartitions 函数来计算不同的分法。最后，我们将结果输出。

总结

本文详细介绍了 NOIP2001 提高组第二题 - 数的划分的算法解析，并提供了 C++ 代码实现。我们使用递归的方法解决问题，并深入分析了代码逻辑，帮助你理解算法的核心思想。希望本文能够帮助你更好地理解和解决此类问题。