用递归法计算从 n 个人中选选 k 个人组成一个委员会的不同组合数.
分析
由 n 个人里选 k 个人的组合数 = 由 n-1 个人里选 k 个人的组合数 + 由 n-1 个人里选 k-1 个人的组合数;
当 n = k 或 k = 0 时, 组合数为 1.
此递归算法在递归过程中会有大量的重复计算, 所以在输入的 n,k 值过大时, 需要大量的运算时间, 只适合一些简单的求解.
C++ 程序如下:
- #include <iostream>
- using namespace std;
- unsigned comm(unsigned n, unsigned k) {
- if (n <k) return 0;
- else if (n == k || k == 0) return 1;
- else return comm(n - 1, k) + comm(n - 1, k - 1);
- }
- int main() {
- unsigned n, k;
- cin>> n>> k;
- cout << comm(n,k);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2611967.html