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

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

5个回答

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

caozhy
回答这么多问题就耍赖把我的积分一笔勾销了 套用公式怎么可能超时呢
5 年多之前 回复
SFQRM
SFQRM 它显示我超时了
5 年多之前 回复

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

SFQRM
SFQRM 哦,原来是这样啊,请问http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2078道题您有什么好方法吗?谢谢!
5 年多之前 回复

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

SFQRM
SFQRM 谢谢,您知道http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2078道题有什么好方法吗?谢谢!
5 年多之前 回复

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

SFQRM
SFQRM 1 1 2 1 3 1
5 年多之前 回复
SFQRM
SFQRM 样例输入:
5 年多之前 回复
SFQRM
SFQRM 多组测试数据 每组包含两个整数N,M(1<=M<=N<=1000),分别表示持有5元和10元的同学个数。
5 年多之前 回复
SFQRM
SFQRM 教学楼有一台奇怪的自动售货机,它只售卖一种饮料,单价5元,并且只收5元、10元面值的货币,但是同学们都很喜欢喝。这个售货机里没有多余的找零,也就是说如果一个持有10元的同学第一个购买,则他不能获得5元找零,但是如果在他之前有一个持有5元的同学买了这种饮料,则他可以获得5元找零。 假设售货机的货源无限,每人只买一罐,现在有N个持有5元的同学和M个持有10元的同学想要购买,问一共有多少种排队方法可以让每个持有10元的同学都获得找零。(这里的排队方法以某一位置上人持的钱数来分,即只要同一位置上的同学所持钱的数目相同,就算同一种排队方法)
5 年多之前 回复
SFQRM
SFQRM 您方便留QQ吗?发给您
5 年多之前 回复

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,然后将两者结果组合起来。

立即提问
相关内容推荐