2 qq 34033296 qq_34033296 于 2016.04.29 00:42 提问

求助!求如何秒杀十万的阶乘?

要求是在一秒钟以内计算出十万的阶乘。我试了直接累乘,需要268秒。尝试完全的因式分解,将其分解为一系列素数的次方相乘,在其中第一项为2的99998次方,用二分乘法需要0.2秒,不可能做到一秒内计算出结果。我觉得我是思路问题,求助如何解秒杀十万的阶乘?

2个回答

caozhy
caozhy   Ds   Rxr 2016.04.29 03:25

查表法。将0~10万每1000的阶乘预先算好了记录下来。只需要100个数据,几乎不要什么存储,就可以保证10万以内的阶乘计算都是秒杀。即便计算10万以上,也可以明显提速。
这个方法其实用在一些科学计算器上,以前我有个卡西欧计算器,就缓存了30和70的阶乘,所以计算70是秒出,计算69反倒有些顿。

qq_34033296
qq_34033296 回复caozhy: 嗯,不过还是觉得有点取巧,谢谢你啊。
一年多之前 回复
caozhy
caozhy   Ds   Rxr 2016.04.29 03:26

一秒钟以内计算出十万的阶乘。我试了直接累乘,需要268秒,这也太夸张了,你用的什么语言?
windows xp自带的计算器,就是呆算实现的,10万的阶乘也就几秒钟,甚至xp x64版,10万的阶乘还能秒出(x64的优势在这里发挥出来了)。
而且你还可以用多线程,这特别适合并行计算。

qq_34033296
qq_34033296 回复caozhy: 我是用c语言写的,因为最后结果很大,有46万多位,所以开了一个500000的数组保存中间结果。每次用下一个数与结果中每一位依次相乘,然后整理进位,这样用了268秒。我之后修改了下,用10000进制,时间为56秒,至少用的是10进制。
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!