C++ 递归算法计算组合数 - 从 n 个人中选 k 个人

#include <iostream>
using namespace std;

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

int main() {
    int n, k;
    cout << '请输入 n 和 k：' << endl;
    cin >> n >> k;
    cout << '从' << n << '个人中选择' << k << '个人组成一个委员会的不同组合数为：' << comm(n, k) << endl;
    return 0;
}

该代码使用递归函数 comm(n, k) 来计算从 n 个人中选择 k 个人的组合数。递归公式如下：

(1) 由 n 个人里选 k 个人的组合数 = 由 n-1 个人里选 k 个人的组合数

• 由 n-1 个人里选 k-1 个人的组合数

(2) 当 n == k 或 k == 0 时，组合数为 1

代码中，comm(n, k) 函数首先判断 k 是否为 0 或者 n 是否等于 k，如果是，则返回 1。否则，递归调用 comm(n - 1, k) 和 comm(n - 1, k - 1)，并将它们的结果相加返回。

在 main() 函数中，程序首先提示用户输入 n 和 k，然后调用 comm(n, k) 函数计算组合数，并输出结果。