C++代码实现计算组合数（3种计算方式）

题目：

输入两个非负整数n和m，返回组合数\(C^m_n\)。例如当n = 10, m = 2时，答案为45。

组合与排列

先从排列数开始说起，排列数是指从n个不同的元素中任意取出m(\(m \leq n\))个元素的所有不同排列的个数。

由定义可知，排列数的公式为：\(A^m_n = n * (n - 1) * ... * (n - m - 1) = \frac{n!}{(n - m)!}\)

组合数和排列数的区别在于组合数与元素的顺序无关，排列数与元素的顺序有关。

可以得到组合数的公式为：\(C^m_n = \frac{A^m_n}{A^m_m} = \frac{n!}{m!(n - m)!}\)

三种计算方式：

1. 通过定义式直接计算

先计算 \(n!\)，然后分别计算\(m!\)和\((n - m)!\)，然后在进行相除即可。计算量较大，容易溢出。

/***
 * Author : DL1024
 * Date   : 2022-11-11
 * ***/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll Combination(ll n, ll m){
    ll res = 1;
    for (ll i = 1; i <= n; ++i) res *= i;
    for (ll i = 1; i <= m; ++i) res /= i;
    for (ll i = 1; i <= n - m; ++i) res /= i;
    return res;
}

int main( ){

    int m = 5, n = 10;
    cout << Combination(n, m) << endl;
    return 0;
}

2. 通过递推公式计算

利用公式 $$C^m_n = C^m_{n-1} + C^{m-1}_{n-1}$$ 进行计算；

/***
 * Author : DL1024
 * Date   : 2022-11-11
 * ***/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll Combination(ll n, ll m){
    if (m == 0 || m == n) return 1;
    return Combination(n - 1, m) + Combination(n - 1, m - 1);
}

ll res[67][67] = {0};   // 备忘录改进

ll Combination1(ll n, ll m){
    if (m == 0 || m == n) return 1;
    if (res[n][m] != 0) return res[n][m];
    return res[n][m] = Combination(n - 1, m) + Combination(n - 1, m - 1);
}

int main( ){

    int m = 5, n = 10;
    cout << Combination(n, m) << endl;
    return 0;
}

3. 分母上下同时进行处理

/***
 * Author : DL1024
 * Date   : 2022-11-11
 * ***/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll Combination(ll n, ll m){
    ll res = 1;
    for (ll i = 1; i <= m; ++i){
        res = res * (n - m + i) / i;        // 先乘后除
    }
    return res;
}

int main( ){

    int m = 5, n = 10;
    cout << Combination(n, m) << endl;
    return 0;
}