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 |
#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 |
#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
;
}
|