以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  [求助]N!的最高位  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=56205)

--  作者：guhongfeixue
--  发布时间：11/29/2007 10:41:00 PM

--  [求助]N!的最高位
Time Limit:1000MS Memory Limit:30000KB

Description

求N的阶乘的最高位数。
例如：
5!=120,所以最高位为1
10!=3628800，所以最高位为3

Input

每个数据包含一行,每行有一个整数N(0<=N<=10000000)

Output

对于每个测试数据，输出N!的最高位数字

Sample Input

5
10  

Sample Output

1
3
请给个高效的算法，谢谢

--  作者：yoonit
--  发布时间：12/13/2007 7:30:00 PM

--  
求阶乘的一般高效算法是
相乘的两个数尽可能的相似
尽可能的用乘方代替乘法
譬如
10!  =  (((2^2)  *  3)^2  *  5)^2  *  7
这样会大大减少运算次数

其次是用一个long double来存储乘积的值 数字过大的时候就除以10 反正我们要的目标是最高位
不知道还有没有 更高的算法

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms