大数阶乘的算法

K8vz}?{4kG0原来做过的一个算法：大数的阶乘，如1000的阶乘51Testing软件测试网X#S b A:B

)Fu`c]AHY0看起来好像比较简单，一个递归就可以实现，但真的是这样么？仔细看看，发现数据类型的范围远远不能满足计算结果的长度，这才是这个算法的核心，那么该如何实现呢？

思路如下：51Testing软件测试网9oD!^0c4j7e}'z+}-N

利用一个数组保存计算结果，然后逐位输出51Testing软件测试网2uFS0csp^P
D

1）利用LOG函数计算出阶乘结果的位数，用这个值初始化一个数组51Testing软件测试网%|a0T@&~#I"@MBq kL

s0H2jEwf"\nBa5Z02）按位进行计算并进行进位处理

[XqW9n&w A03）逐位输出数组的每个值拼装成计算结果51Testing软件测试网mI/UrQ*v
N4Z:t

VBS代码：51Testing软件测试网F&^"]e2s!u.]LsF

Function Factorial(n) 
-jx'd%C+PI0 '处理计算结果 
JE}@YYI*u+vP0 Sum = 1.051Testing软件测试网nqH/Md&u1[#t5J
 Str = ""
U(ry*c+qeX)AJ0V0 For z = 1 To n
l0fV.Z:TTn0  Sum = Sum + (Log(z)/Log(10))
)j^$G7o'O!`0 Next 51Testing软件测试网(KC;JF2S
 Sum = Int(Sum)
#z2w0\s?I `!y$Wxg0 '初始化存储数组51Testing软件测试网wGV,A&@ dmD
 ReDim ArrValue(Sum)51Testing软件测试网:wz%[R2b`FmX
 ArrValue(0) = 151Testing软件测试网+V!Uc/?z'@I
 For x = 1 To Sum51Testing软件测试网a:W Gh7n3V{
  ArrValue(x) = 051Testing软件测试网;XW:axIF0L
 Next51Testing软件测试网'N]MSy*rV t

&?3T%MS/[(u0~TP0 '按位计算结果51Testing软件测试网S;H`yb3c.oK
 For i = 1 To n51Testing软件测试网e)|!p2?Q+D
  MultiValue = 0
v/IR(F,dm0  Length = Length + (Log(i)/Log(10))51Testing软件测试网-gB M nh N;{B8`
  For j = 0 To CInt(Length)51Testing软件测试网 h0}1~Us9c@i
   MultiValue = MultiValue + (i * ArrValue(j)) 51Testing软件测试网Bl,~b5O~DOu
   ArrValue(j) = Int(MultiValue) Mod 10
R wE&JI4bSd I,u0   MultiValue = MultiValue / 10
4Q\4ebC%w+f2s0  Next 51Testing软件测试网
^H,j6GBK.A5G8xo!_
 Next51Testing软件测试网e
F4Z%Q E[
 51Testing软件测试网s]F!u*p3G2Z3@
 For k = Sum-1 To 0 Step -1
4{z;co;QY0  Str = Str & ArrValue(k)
5_#^W^ RC6{,R,O0 Next
2e q%Z`'Y$v|Cg M0 Factorial = Str51Testing软件测试网0CZ5f$X^P6_xM
End Function51Testing软件测试网ka#n/|)w

注意红色部分，考虑下为什么要用Int转换呢？

仔细想想，呵呵，对了，是为了避免四舍五入出现的进位错误

C#代码：51Testing软件测试网oO-ZEh9z

using System;

UO5PekB`0namespace arithmetic
x:j @+S7SY0{
ubEp@j5{@YC ^0    /// <summary> 51Testing软件测试网y,a@:w9n.V+^.r;NJ
    /// 大数阶乘计算。
uW Gm^0    /// </summary>
-s*^L7n4U.r*m0    class factorial
(H w2[!B+B+tTOxqh0    {
W N2g{vH!J9I-UA0        /// <summary> 51Testing软件测试网nIT"J&D%O+~c
        /// 应用程序的主入口点。
V_
O'~+V0        /// </summary> 51Testing软件测试网
t_!KoCP

        //方法1：GetNumber获取需要进行阶乘的数字
$NWC8e1M0        public static int GetNumber()51Testing软件测试网1`*j(^K[
        {
T
m;K-n U8g&a(b0            int n;
N8SzQa%P6w C+o1E0            Console.WriteLine("请输入n值:");51Testing软件测试网,j nuG+Hw;]}
            n = Convert.ToInt32(Console.ReadLine());51Testing软件测试网2n@B@;V&S Tz0f3{

0F9x&[vW9{'eJ6p0            while (n <= 0)
7^P3I#kLO0            {51Testing软件测试网E/DCrO,q)tx.f
                Console.WriteLine("请重新输入n值:");51Testing软件测试网/UsT2}}:aLb
                n = Convert.ToInt32(Console.ReadLine());51Testing软件测试网]d$k5e4B0p1{Axs
            }51Testing软件测试网^2Yx
G"f^%o
            return n;
wl kT1R.C0        }51Testing软件测试网iS/WZTG^0vex

$`N8|;q'z1L)R_2uN0        //方法2：GetLength获取计算结果的位数
-n'@jKH,iuyS0        public static int GetLength(int n)

y$X/e&G(i d$t7x.nJ0        {
8Z.x/a/d c `.eym*Y0            double sum = 1.0;
#C#~7e]MI:jO0            for (int i = 1; i <= n; i++)51Testing软件测试网Y ^1?'x
O8ZuZF"E
            {51Testing软件测试网M b)yuSU
                sum += Math.Log10((double)i);
R]zWz
`
J0            }
!M2Imp/t;I7RgP0            return ((int)sum);51Testing软件测试网@8HCXC2WNO
        }51Testing软件测试网$aD4RmJ$r2w1e4?#A

        //方法3：Init初始化存储结果的数组
`U7Vb2c }R0        public static byte[] Init(int length)51Testing软件测试网/k;}5N:l,C
        {51Testing软件测试网"fg0nyp
            byte[] arrValue = new byte[length];
z0v'z#U ~F)i(E
S0            arrValue[0] = 1;51Testing软件测试网,@jn&iCdfG(D.S*f
            for (int i = 1; i < length; i++)51Testing软件测试网D2T.L1Z {
v6j
            {51Testing软件测试网NH:Fm'Xrq
                arrValue[i] = 0;51Testing软件测试网'_.UXRT/\T
            }
'z+w,fz(rUmW0            return arrValue;
z(_xDHQ6Y0        }51Testing软件测试网j;Y1_)Q1R[;N q

F!XG!]n4U0        //方法4：GetCarrier俺位计算结果并进行进位处理 
r{.I Cmm:Ym/[M0        public static byte[] GetCarrier(byte[] arrValue, int n)
0\S@h ?S0        {
Zc~3B6G4Ixq0            double length = 1;51Testing软件测试网bP
XF
me_$Z:L
            for (int i = 1; i <= n; ++i)51Testing软件测试网ap'B~4oY
            {51Testing软件测试网B$KI x(IP;R]-Y p1u,m.E
                long multiValue = 0;51Testing软件测试网G1~y"sk.jx
                length += Math.Log10((double)i);51Testing软件测试网u5V`P8Jl`R7ag

                for (int j = 0; j < (int)length; ++j)51Testing软件测试网]{mRi
                {
NP2r Sd OC0                    multiValue += (i * arrValue[j]);51Testing软件测试网8Wojv%i)m:c2S2}
                    arrValue[j] = (byte)(multiValue % 10);
X0s(_:R4~0                    multiValue /= 10;51Testing软件测试网%E.I BnG`
                }
Kv6v8iRY0            }
T*O:_6I i0            return arrValue;
ZAE0hr0o6RU'a2O;Z H0        }51Testing软件测试网mn~9Y"S

        //方法5：GetValue计算结果 51Testing软件测试网gMM"N V?y+J
        public static byte[] GetValue(int val)
S%T*b(M2d
rMm0        {51Testing软件测试网QuY9e|;d-d+k}O"t
            int length = GetLength(val);
G-};c7~8L.qgIztu0            //byte[] arrValue = new byte[length]; 51Testing软件测试网~ T.]*Q3G'V#w8UnW-z
            byte[] arrValue = Init(length);

            arrValue = GetCarrier(arrValue, val);
[D7o(L {8E0            return arrValue;51Testing软件测试网,x
c*d$Gh7\P
        }51Testing软件测试网3_-C#u8YF

        [STAThread]
1n!^c"E9N5fY0        static void Main(string[] args)51Testing软件测试网
D&O-|P4o
        {51Testing软件测试网h`~;vjG6w
            while (true)
_vXa2i-wV-P+~0            {51Testing软件测试网 w4XY3W lBV
                int n = GetNumber();
fMXR%t/o }z%E#n/xd0                int length = GetLength(n);
6m!C6rn-v6f7i }~7`;l0                byte[] buff = Init(length);51Testing软件测试网P)T E"Q~L
                buff = GetValue(n);
{&VcB*j4zm0                for (int i = length - 1; i >= 0; i--)
1X7e
}*W)v L&y0                {51Testing软件测试网,NU9FE k
                    Console.Write("{0}", buff[i]);
0yP0xU{EY)AIm0                }
H&SyGO7P1RQ0            }51Testing软件测试网.yr*vR_vX8~"`
        }51Testing软件测试网$_V/ZS-^&xN"@
    }51Testing软件测试网-m6qX\G%`3@
BU
} 51Testing软件测试网 J ]DvW8{Q_

P6J*Z'~#Z8i%y}F0