组合数的两种计算方法(递推,对数)

时间:2021-09-07 14:52:58


http://blog.csdn.net/Feynman1999/article/details/56679096

组合数

       从m个不同元素中,任取n(n≤m)个元素并成一组,叫做从m个不同元素中取出n个元素的一个组合;所有可能的组合种数就是组合数。组合数的计算公式如下图:

组合数的两种计算方法(递推,对数)

式子中出现了阶乘,而20!=2.4329020081766 * 1018    

这个数字已经和long long能表示的最大整数一个数量级了,而式子是个除式,所以要想办法在过程中把数降下来。



方法一:想到一个组合数公式:

c(m,n)=c(m-1,n-1)+c(m-1,n)

这个式子可以这样记忆:你从m个元素里挑n个元素,针对第一个元素要么是n个里的要么不是,如果是的,那么就从剩下的m-1个里挑n-1个 就是c(m-1,n-1);如果第一个元素不是n里的,就从剩下的m-1个元素里挑n个,就是c(m-1,n)。

利用这个公式,就能用递归的方法解决问题。注意递归的结束条件。

代码示例:

  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
          
#include<iostream>
#include<cstdio>
using namespace std ;
long long comb ( int m , int n )
{
if ( n == 0 ) return 1 ;
if ( n == 1 ) return m ;
if ( n > m / 2 ) return comb ( m , m - n );
if ( n > 1 ) return ( comb ( m - 1 , n - 1 ) + comb ( m - 1 , n ));
}
int main ()
{
int m , n ;
while ( cin >> m >> n )
cout << comb ( m , n ) << endl ;
return 0 ;
}
 来自CODE的代码片
comb1.cpp



方法二:
因为公式右边均为乘法,相到可以取对数将其展开。于是对公式两遍取对数,log(c(m,n))= log( m!/(m-n)!) -log n!
于是可以直接求 log(m-n+1)+log(m-n+2)+······+log(m)  和log(1)+log(2)+······+log(n)。
注意这里的log()和exp()函数在头文件#include<math.h>中,log()默认是以2为底,如果要求以a为底b的对数,可以用对数的性质转换下
:log(a)b=logb/loga。

代码示例:

  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
           
#include<iostream>
#include<math.h>
using namespace std ;
double comb_log ( int m , int n ) //对数求法
{
int i ;
if ( n > m - n ) n = m - n ;
double s1 = 0.0 , s2 = 0.0 ;
for ( i = m - n + 1 ; i <= m ; ++ i ) s1 += log ( i ); //求 log( m!/(m-n)!)
for ( i = 1 ; i <= n ; ++ i ) s2 += log ( i ); // 求log n!
return exp ( s1 - s2 );
}
int main ()
{
int m , n ;
while ( cin >> m >> n ){
cout << ( long long )( comb_log ( m , n )) << endl ;
}
return 0 ;
}