求组合数的方法:转载自VincentCZW的博客
遇到了就查了下:地址:http://www.cnblogs.com/BeyondAnyTime/archive/2012/05/18/2508189.html
求一个组合数Cnm的值,Cnm= n! /(n-m)!*m!化简的结果为
Cnm = (n*(n-1)*…*(n-m+1))/m!
这个直接求根据公式直接求显然是不行的,当n和m较大时,显然是要溢出的。目前知道两种解决这种题的思路:
思路一:可以利用递推关系式Cnm = C(n)(m-1) + C(n-1)(m-1)来实现,这样初始化前几个组合数,在根据题目要求处理的最大n和m值,递推求出所有的Cnm,并保存。
实现方法以后补上。
思路二:为了避免直接计算n的阶乘,可以直接对公式两边取对数,于是得到:ln(C(n,m)) = ln(n!) - ln(m!) - ln( (n-m)! )
对数有性质:ln(x*y) = ln(x) + ln(y),因此转化成:
Ln(n!) = ln(1) + ln(2) + …+ln(n);
同理消去重叠的部分得到:
Cnm = (n*(n-1)*…*(n-m+1))/m!
因此这个算法时间复杂度仍然是 O( m ),虽然浮点计算比整数计算要慢,但解决了整数计算的溢出问题。
代码实现(转)
double cnm_lg(int n,int m)
{
int i;
double s1=0.0,s2=0.0;
for(i=1;i<=m;i++)
s1 += log(i);
for(i=n-m+1;i<=n;i++)
s2 += log(i);
return s2-s1;
}
double cnm_double(int n,int m)
{
if(m > n/2)
m = n-m;
return exp(cnm_lg(n,m));
}
最新文章
- Oracle死锁
- 关于SharpDevelop 4版本以上没有ILAsm模板项目问题
- 【OC简介-类和对象】
- nginx下面server配置
- iOS多线程的初步研究(五)-- 如何让NSURLConnection在子线程中运行
- class int
- Ruby基础数据类型
- IIS7.5 asp+access数据库连接失败处理 64位系统
- 浅析Python中的struct模块
- hdu1047 Integer Inquiry 多次大数相加
- Selenium常用API详解介绍
- 小程序之hover-class
- [20181007]12cR2 Using SQL Patch 2.txt
- SCOI 2015 Day2 简要题解
- Java坦克大战(三)
- 以添加评论组件为例看angular2请求数据的处理
- CM5.x配置spark错误解决
- CSS3 鼠标划上图片放大
- Java ArrayList、string、string[]之间的转换
- maven本地库更新失败