由n个人里选k个人的组合数
(2009-02-09 16:19:47)
标签:
组合数k-1cinit |
分类: 算法 |
由n个人里选k个人的组合数 = 由(n-1)个人里选k个人的组合数+由(n-1)个人里选(k-1)个人的组合数.
原理:
由n个人选k个人:
假设第1个人被选中,那么就要从其余n-1个人里选k-1个人,有C(n-1,k-1)种选法;
假设第1个人没被选中,那么就要从其余n-1个人里选k个人,有C(n-1,k)种选法;
递归调用:
#include <iostream>
using namespace std;
int main()
{
int n, k;
int comm( int n, int k );
cin >> n
>> k;
cout << comm( n,k )
<< endl;
system( "pause" );
}
int comm( int n, int k )
{
if( k>n )
return
0;
else if( n == 0 || k == 0 )
return
1;
else
return comm(
n - 1, k ) + comm( n - 1, k - 1 );
}
原理:
由n个人选k个人:
假设第1个人被选中,那么就要从其余n-1个人里选k-1个人,有C(n-1,k-1)种选法;
假设第1个人没被选中,那么就要从其余n-1个人里选k个人,有C(n-1,k)种选法;
递归调用:
#include <iostream>
using namespace std;
int main()
{
}
int comm( int n, int k )
{
}