我也来晒个计算阶乘的类，可以精确计算大数的阶乘，10000的阶乘只要1.3秒左右
本文内容详见：http://blog.csdn.net/Snowdust/archive/2010/03/18/5392444.aspx
关于阶乘，老郭和宝宝等前辈做了大量研究，计算速度也达到了非常快的水准。本文宗旨不在于和他们比快，因为他们专门为阶乘做了很多优化。本文介绍的是使用C#直接计算的方法，速度虽然不能跟他们相比，但在一般场合下使用应该是足够的。本文的思想其实是ACM中的一个基本函数，做了一定改动。
这个类中用到了10000进制表示法，我做了一定的尝试，发现在100000进制的情况下速度最快，以下是耗费时间统计表(单位：ms)，其中列表示要计算的阶乘，行表示进制。
用这个类计算100000!花费263819.2536ms，结果见：http://blog.csdn.net/Snowdust/archive/2010/03/18/5392444.aspx
代码如下：
- C# code
//-----------------------------------------//// 算法：阶乘类//// 版权所有(C) Snowdust// 个人博客 http://blog.csdn.net/snwodust & http://snowdust.cnblogs.com// MSN & Email snwodust77@sina.com//// 此源代码可免费用于各类软件（含商业软件）// 允许对此代码的进一步修改与开发// 但必须完整保留此版权信息//// 调用方法如下：// int num = 10000;// Arithmetic.Factorial f = new Arithmetic.Factorial(num);// List<int> result = f.Calculate();// String ret = f.ToString();// 返回结果：result为100000进制表示的范型，ret为转换成十制制的字符串//// 版本历史：// V0.1 2010-03-17 摘要：首次创建 ////-----------------------------------------using System;using System.Collections.Generic;using System.Text;namespace Arithmetic{ public class Factorial { #region 定义属性 /// <summary> /// 进制 /// </summary> private int m_BaseNumber = 100000; public int BaseNumber { get { return m_BaseNumber; } } /// <summary> /// 待求阶乘的数 /// </summary> private int m_Number; /// <summary> /// 结果 /// </summary> private List<int> m_Result = new List<int>(); #endregion #region 构造函数 /// <summary> /// 构造函数 /// </summary> /// <param name="n">待求阶乘的数</param> public Factorial(int n) { m_Number = n; m_Result = new List<int>(); } #endregion #region 方法 /// <summary> /// 计算阶乘 /// </summary> /// <returns>结果范型</returns> public List<int> Calculate() { int digit = (int)System.Math.Log10(m_BaseNumber); int len = (int)(m_Number * System.Math.Log10((m_Number + 1) / 2)) / digit;//计算n!有数数字的个数 len += 2; //保险起见，加长2位 int[] a = new int[len]; int i, j; long c; int m = 0; a[0] = 1; for (i = 2; i <= m_Number; i++) { c = 0; for (j = 0; j <= m; j++) { long t = a[j] * i + c; c = t / m_BaseNumber; a[j] = (int)(t % m_BaseNumber); } while (c > 0) { m++; a[m] = (int)(c % m_BaseNumber); c = c / m_BaseNumber; } } for (i = 0; i <= m; i++) { m_Result.Add(a[i]); } return m_Result; } /// <summary> /// 重写ToString方法 /// </summary> /// <returns>结果字符串</returns> public override string ToString() { if (m_Result.Count == 0) { Calculate(); } StringBuilder sb = new StringBuilder(); int digit = (int)System.Math.Log10(m_BaseNumber); sb.Append(m_Result[m_Result.Count - 1]); for (int i = m_Result.Count - 2; i >= 0; i--) { sb.Append(m_Result[i].ToString().PadLeft(digit, '0')); } return sb.ToString(); } #endregion }} [解决办法]
占个沙发
[解决办法]
没看懂。
先占位学习。
[解决办法]
抢个板凳
速度的学习下
[解决办法]
收藏...........................
[解决办法]
我是来接分学习滴
[解决办法]
占个位！MS04年有个高人发过一个类似的代码！！
[解决办法]
循环内定义变量也耗时
当 m_Number数据量大的时候这个时间也就不小了
[解决办法]
只看到了定义了个局部变量叫 sb
[解决办法]
哈 ·
[解决办法]
标记~
[解决办法]
站位学习
[解决办法]
不知道楼主的 10000! 1.3s 包含输出不?
hehe,我之前也发过一篇
用的是递归,直接相乘的方式
速度有些慢,呵呵 10000! 5.5s(包含输出)
顶,支持lz
http://blog.csdn.net/Lost_Painting/archive/2010/02/09/5302815.aspx
[解决办法]
学习.....
[解决办法]
收藏...........................
[解决办法]
学习..........
[解决办法]
学习
教您如何更快获得可用分
[解决办法]
恩，非常不错啊
[解决办法]
[解决办法]
[解决办法]
支持。
[解决办法]
学习下
[解决办法]
收藏下
[解决办法]
学习一下~！
[解决办法]
不错不错，呵呵，又学习了
[解决办法]
果然高手如云啊
[解决办法]
学习....................
[解决办法]
我是来接分学习滴
[解决办法]
占位先
[解决办法]
没学过，看不懂
[解决办法]
先留个记号，以后慢慢研究
[解决办法]
看看学习学习，慢慢研究，
[解决办法]
果然高手如云啊
[解决办法]
先留个记号，以后慢慢研究
[解决办法]
看看 在研究研究
[解决办法]
不错不错啊，学习
[解决办法]
先标记一下，明天再研究！
[解决办法]
- C# code
mark
[解决办法]
学习 收藏
[解决办法]
我是来接分学习滴
收藏
[解决办法]
学习 收藏````
[解决办法]
牛B
以前看见一个算法
我测试了下10W的阶乘用了7分钟左右
[解决办法]
[解决办法]
又见大数阶乘
[解决办法]
嗯，不错哈
[解决办法]
学习~~
[解决办法]
犀利，学习~~
[解决办法]
逛下水
[解决办法]
厉害
[解决办法]
Mark
[解决办法]
[解决办法]
学习学习~~~~
[解决办法]
支持一下~~~~~
[解决办法]
不错哈~
[解决办法]
接分来了
[解决办法]
CPU好的跑的更快吧。
[解决办法]
还行 正要考计算机二级
[解决办法]
Mark
[解决办法]
坐下来 慢慢看
[解决办法]
犀利，学习~~
[解决办法]
收藏，研究一下
[解决办法]
我是路过 打酱油的 ..
[解决办法]
收藏了
[解决办法]
学习学习
------解决方案--------------------
[color=#FF9900][/color]收藏
[解决办法]
学习下
[解决办法]
用C#写算法的并不多见！不错，帮顶一下！
[解决办法]
还记得当时大二做课程设计时有道题就是大数阶乘的，但当时没好好学，也没做起来
[解决办法]
采用移位可能更快
[解决办法]
收藏本文，学学。
[解决办法]
MARK
[解决办法]
kankan 看看啊/
[解决办法]
学习了
[解决办法]
学习一下
[解决办法]
学习。。。。。。。
[解决办法]
每天回帖即可获得10分可用分！
[解决办法]
81
[解决办法]
学习了，谢谢楼主哦
[解决办法]
学习学习
[解决办法]
学习下~~~~~~~~~~~~~~·
[解决办法]
我来顶个，学习了，呵呵，希望有更好的
[解决办法]
看得头疼。
[解决办法]
不错 顶lz 学习啦～～～
[解决办法]
ding ,,,,,,,,,,,,,,,
[解决办法]
这会儿懒得看
先顶一顶
记得给分哦
[解决办法]
虽然用不到,学习了
[解决办法]
学习 ~~ 谢谢楼主
[解决办法]
对c#了解一些，可以把参考java上
[解决办法]
厉害，收藏学习下
[解决办法]
学习，好东西！
[解决办法]
学习 ~~ 顶楼主！
[解决办法]
这也能被你想到。。。。
高
[解决办法]
这也能被你想到。。。。
高
[解决办法]
看来C#真的很烂啊。
随便写个Java的，没有经过任何优化。
- Java code
public class Factorial { public static void main(String[] args) { long start =System.currentTimeMillis(); int i = 10000; BigInteger big = new BigInteger(Integer.toString(i)); for (int j = i - 1; j > 1; j--) { big = big.multiply(new BigInteger(Integer.toString(j))); } long end = System.currentTimeMillis(); System.out.println("run time: "+(end-start)+"ms"); System.out.println(big.toString()); System.out.println("show time: "+(System.currentTimeMillis()-end)+"ms"); }}
[解决办法]
[解决办法]
学习了！