C++ 实现炮弹装入炮口的方案数计算

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> using namespace std; // 递归函数，用于计算将 m 个炮弹放入 n 个炮口的方案数 int countWays(int m, int n) { // 如果炮弹数为 0，只有一种方案，即所有炮口都为空 if (m == 0) { return 1; } // 如果炮口数为 0，没有炮弹可放，方案数为 0 if (n == 0) { return 0; } // 如果炮弹数小于炮口数，方案数等于将 m 个炮弹放入 m 个炮口的方案数 if (m < n) { return countWays(m, m); } // 两种情况：一种是至少有一个炮口为空，另一种是每个炮口至少放一个炮弹 return countWays(m, n - 1) + countWays(m - n, n); } int main() { int m, n; // 读取输入的炮弹数 m 和炮口数 n cin >> m >> n; // 调用 countWays 函数计算方案数 int result = countWays(m, n); // 输出结果 cout << result << endl; return 0; } ``` ### 代码解释： 1. **递归函数 `countWays`**： - 当 `m` 为 0 时，表示没有炮弹，只有一种方案，即所有炮口都为空，返回 1。 - 当 `n` 为 0 时，表示没有炮口，无法放置炮弹，返回 0。 - 当 `m < n` 时，由于炮口数多于炮弹数，多余的炮口没有意义，所以方案数等于将 `m` 个炮弹放入 `m` 个炮口的方案数。 - 对于其他情况，有两种选择： - 至少有一个炮口为空，即不使用最后一个炮口，方案数为 `countWays(m, n - 1)`。 - 每个炮口至少放一个炮弹，先在每个炮口放一个炮弹，剩下 `m - n` 个炮弹再放入 `n` 个炮口中，方案数为 `countWays(m - n, n)`。 - 最终的方案数是这两种情况的方案数之和。 2. **主函数 `main`**： - 读取输入的 `m` 和 `n`。 - 调用 `countWays` 函数计算方案数。 - 输出结果。 ### 复杂度分析： - **时间复杂度**：由于使用了递归，时间复杂度为指数级，约为 $O(2^m)$。 - **空间复杂度**：递归调用栈的深度为 $O(m)$，因此空间复杂度为 $O(m)$。 ######[AI问答 | 697点数解答 | 2026-03-07 20:41:00]