c++求组合数描述 输入两个整数m,n,求m个数字中选n个数的组合数。(1<=n<=m<=100) 用例输入 1 5 3 用例输出 1 10
时间: 2024-09-08 18:01:50 浏览: 58
在C++中,求组合数可以使用多种方法,其中一种常用且简单的方法是利用递归公式 C(m, n) = C(m-1, n-1) + C(m-1, n),同时利用组合数的性质 C(m, n) = C(m, m-n) 来减少计算量,特别是当n > m/2时。另外,可以使用帕斯卡三角形来递推组合数,或者直接使用公式 C(m, n) = m! / (n! * (m-n)!) 来计算,但直接使用阶乘会涉及到大量的重复计算,因此一般使用递归或者迭代的方式来优化计算过程。
下面是一个使用递归方法的示例代码:
```cpp
#include <iostream>
using namespace std;
int C(int m, int n) {
if (n == 0 || n == m) {
return 1;
} else {
return C(m - 1, n - 1) + C(m - 1, n);
}
}
int main() {
int m, n;
cin >> m >> n;
cout << C(m, n) << endl;
return 0;
}
```
这段代码中,函数C是用来计算组合数的递归函数。为了避免重复计算,可以使用动态规划的方法,将已经计算过的组合数存储起来以备后用。
另外,由于问题中提到的是1<=n<=m<=100,直接使用递归可能会导致大量的重复计算和栈溢出的风险。因此,实际应用中可以使用动态规划优化过的代码,或者使用迭代的方式计算阶乘来避免递归的复杂性。
阅读全文