c++组合数

### 计算组合数的C++实现 在C++中，可以通过多种方式来计算组合数 $ C(n, k) $。以下是几种常见的方式及其具体实现。 #### 方法一：基于公式的直接计算 通过公式 $ C(n, k) = \frac{n!}{k!(n-k)!} $ 来计算组合数是一种简单直观的方法。然而需要注意的是，在处理大数值时可能会遇到溢出问题。因此可以在计算过程中逐步取模以减少中间结果的大小。 ```cpp #include <iostream> using namespace std; long long factorial(int num) { long long result = 1; for (int i = 2; i <= num; ++i) { result *= i; } return result; } long long combination_formula(int n, int k) { if (k > n) return 0; return factorial(n) / (factorial(k) * factorial(n - k)); } int main() { int n = 5, k = 3; cout << "Combination using formula: " << combination_formula(n, k) << endl; return 0; } ``` 这种方法虽然易于理解，但在性能上并不高效，尤其是在面对较大的输入数据时[^2]。 --- #### 方法二：递归法 利用递推关系 $ C(n, k) = C(n-1, k-1) + C(n-1, k) $ 和边界条件 $ C(n, 0) = C(n, n) = 1 $ 实现递归算法。尽管该方法逻辑清晰，但由于重复子问题的存在可能导致时间复杂度较高。 ```cpp #include <iostream> using namespace std; long long combination_recursive(int n, int k) { if (k == 0 || k == n) return 1; return combination_recursive(n - 1, k - 1) + combination_recursive(n - 1, k); } int main() { int n = 5, k = 3; cout << "Combination using recursion: " << combination_recursive(n, k) << endl; return 0; } ``` 此方法适合用于教学目的或者小规模输入的情况[^1]。 --- #### 方法三：动态规划 为了避免递归中的冗余计算，可以采用自底向上的动态规划策略构建二维表 `dp`，其中 `dp[i][j]` 表示从 `i` 中选取 `j` 的组合数。这种方式的时间复杂度为 O(n*k)，空间复杂度同样为 O(n*k)。 ```cpp #include <iostream> #include <vector> using namespace std; long long combination_dp(int n, int k) { vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0)); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= min(i, k); ++j) { if (j == 0 || j == i) dp[i][j] = 1; else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } return dp[n][k]; } int main() { int n = 5, k = 3; cout << "Combination using DP: " << combination_dp(n, k) << endl; return 0; } ``` 上述代码展示了如何通过动态规划有效解决组合数问题，并且能够显著提升运行效率[^3]。 --- #### 性能比较与优化建议 对于大规模输入，推荐优先考虑动态规划或其他更高效的算法变体（如仅保留当前行的状态），从而降低内存消耗并提高执行速度。 ---