SFQRM
2015-03-29 08:48
采纳率: 25%
浏览 3.3k
已采纳

c语言求组合数,但是超了,求大神指点!

我用递归写出了求组合数,c(5,3),c(6,2)之类的能算出来,但是c(1024,512)这种大数就算不出来了,超时很严重,而且取模之后也不行,求大神们指点啊!!谢谢!!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

5条回答 默认 最新

  • blownewbee 2015-03-29 09:03
    已采纳

    它只问多少种,没有让你列出多少种,这是数学问题不是编程问题。直接套公式。

    点赞 评论
  • blownewbee 2015-03-29 08:53

    c(1024,512)没有任何算法能做到。
    C(100, 50)已经达到10^29了,而C(1024,512)几乎是天文数字。
    假设计算机每秒能计算1万亿次,每次计算都直接输出一种结果,那么运算时间也需要用年来衡量。

    点赞 评论
  • blownewbee 2015-03-29 08:56

    这里有排列组合计算公式(中学就学过,可以复习下)
    http://www.cnblogs.com/qlee/archive/2011/08/31/2161306.html
    然后自己拿计算器(一般的科学计算器算不了那么大的阶乘,推荐XP自带的计算器的科学计算功能)算算1024!是什么概念

    点赞 评论
  • blownewbee 2015-03-29 08:57

    你给的链接看不到题。能转载出来么

    点赞 评论
  • yufeng_li 2015-03-29 12:32

    c(1024,512)这种运算本身复杂度并不高,只需要1024次乘法加一次除法运算,对于计算机来说应该是ms级别的。但是数太大会溢出,这个你就需要做一些特殊处理了。下面的方法你可以尝试如下方法:
    方法 1,直接实现大数运算。
    方法2,先对将分母512!从分子中约去,然后再用大数计算。
    方法3,利用C(m,n)=C(m-1,n)+C(m-1,n-1)来计算
    方法3,对C(m,n)取log运算,然后再进行指数运算。这样计算的结果可能不精确。可以选个合适的P,计算出C(m,n)%P,然后将两者结果组合起来。

    点赞 评论

相关推荐 更多相似问题