用递归法计算从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 ;
else if (n == k || k == ) return ;
else return comm(n - , k) + comm(n - , k - );
} int main() {
unsigned n, k;
cin >> n >> k;
cout << comm(n,k);
return ;
}