注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

The Bloom of Youth

本博客已搬家至http://kuangqi.me

 
 
 

日志

 
 

整数运算计算组合数C(n, k)  

2012-01-27 18:00:15|  分类: 编程之美 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
计算组合数C(n, k) = n! / (k! * (n-k)!)
由于用到了阶乘,极容易导致数据溢出,应用中应采用边乘边除的方法。除法一般需要用到浮点数,但通过数论中的定理,可以通过整数运算实现。

int C(int n, int k)

{

    long long s = 1;

    int x = 1;

    if( k > n - k ) k = n - k;

    for(int i = n; i > n - k; i--)

    {

        s *= i;

        s /= x;

        x++;

    }

    return (int)s;

}


代码如下如果想测试你自己的实现,请移步POJ 2249题http://poj.org/problem?id=2249
  评论这张
 
阅读(1021)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018