有關(guān)階乘的算法，不外乎兩個(gè)方面：一是高精度計(jì)算;二是與數(shù)論相關(guān)。
一。 高精度計(jì)算階乘
這實(shí)際上是最沒(méi)有技術(shù)含量的問(wèn)題，但是又會(huì)經(jīng)常用到，所以還是得編寫(xiě)，優(yōu)化它的計(jì)算。
首先看小于等于12的階乘計(jì)算(計(jì)算結(jié)果不會(huì)超出32位范圍)：
int factorial(int n) {
if (n == 1 || n == 0)
return 1;
return factorial(n-1)*n;
}
這個(gè)遞歸程序簡(jiǎn)單明了，非常直觀，然而一旦n > 12，則超過(guò)32位int型的范圍出現(xiàn)錯(cuò)誤結(jié)果，所以上面這個(gè)遞歸程序僅適合n <= 12的階乘計(jì)算，為了計(jì)算較大n的階乘，需要將高精度乘法算法納入到階乘計(jì)算中來(lái)，高精度乘法過(guò)程可以如下簡(jiǎn)單的描述：(其中A * B = C，A[0], B[0], C[0]分別存儲(chǔ)長(zhǎng)度)
for (i = 1; i <= A[0]; i++)
for (j = 1; j <= B[0]; j++) {
C[i+j-1] += A[i]*B[j]; // 當(dāng)前i+j-1位對(duì)應(yīng)項(xiàng) + A[i] * B[j]
C[i+j] += C[i+j-1]/10; // 它的后一位 + 它的商(進(jìn)位)
C[i+j-1] %= 10; // 它再取余即可
}
C[0] = A[0] + B[0];
while (C[0] > 1 && C[C[0]] == 0) C[0]--; // 去頭0，獲得實(shí)際C的長(zhǎng)度
有了這個(gè)高精度乘法之后，計(jì)算階乘就可以簡(jiǎn)單的迭代進(jìn)行：
for (i = 2; i <= n; i++) {
將i轉(zhuǎn)換成字符數(shù)組;
執(zhí)行高精度乘法：將上一次結(jié)果乘上i
}
二。 與數(shù)論有關(guān)
由于階乘到后面越來(lái)越大，巧妙的利用數(shù)論求得一些有趣的數(shù)字(數(shù)值)等成為階乘算法的設(shè)計(jì)點(diǎn)，下面給出幾道相關(guān)的問(wèn)題與分析： www.liuhebao.com
(1) 計(jì)算階乘末尾第一個(gè)非0數(shù)字：
這是一個(gè)比較經(jīng)典的問(wèn)題，比較復(fù)雜的算法是利用一個(gè)艱難的數(shù)學(xué)公式，可惜我不會(huì)，從網(wǎng)上的資料學(xué)習(xí)中，整理出下面這個(gè)簡(jiǎn)單易懂的算法：
觀察n!，可以發(fā)現(xiàn)在乘的過(guò)程中，對(duì)于任意 n > 1，n!的末尾第一個(gè)非0數(shù)字都是偶數(shù)。我們只需保留最后一位非零數(shù)。當(dāng)要乘的數(shù)中含有因數(shù)5時(shí)，我們可以把所有的因數(shù)5都當(dāng)作8來(lái)乘。這是因?yàn)椋?br>
…x2*5=…10(舍)或…60，最后一位非零數(shù)為6。而恰好2*8=16，末位為6。
…x4*5=…70(舍)或…20，最后一位非零數(shù)為2。而恰好4*8=32，末位為2。
…x6*5=…30(舍)或…80，最后一位非零數(shù)為8。而恰好6*8=48，末位為8。
…x8*5=…90(舍)或…40，最后一位非零數(shù)為4。而恰好8*8=64，末位為4。
(對(duì)于n > 1時(shí)，最后一位不會(huì)出現(xiàn) 1, 7, 3, 9，而永遠(yuǎn)是2, 4, 6, 8的循環(huán)出現(xiàn))
因此，在迭代作乘法時(shí)，主要就是計(jì)算因子5的數(shù)量，同時(shí)可見(jiàn)因子5的個(gè)數(shù)以4為循環(huán)節(jié)(即只需要取它的數(shù)量對(duì)4取模)。那么對(duì)于不同情況下的因子5的數(shù)量，可以通過(guò)res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}}來(lái)得到，使用nonzero[i]表示i的階乘的最后一位，那么：
如果t是偶數(shù)，則直接乘：nonzero[i] = (nonzero[i-1]*t)%10。
否則nonzero[i] = res[((nonzero[i-1]*t)%10)/2][five];
其中t是除掉所有因子5的結(jié)果，five為因子5數(shù)量對(duì)4的模。相關(guān)題目：
http://acm.zju.edu.cn的第1222題。不過(guò)這一道題注意的是，它的輸入n并非只在32位int數(shù)值范圍內(nèi)，而是有很大的長(zhǎng)度，所以計(jì)算這道變態(tài)題目時(shí)，需要利用到高精度除法(n/=5)和高精度加法(cnt+=n)。
(2)。 階乘末尾有多少個(gè)0
分析發(fā)現(xiàn)，實(shí)際上形成末尾0，就是因子5的數(shù)量，而計(jì)算1~n之間包含一個(gè)因子i的個(gè)數(shù)的簡(jiǎn)單算法就是：
cnt = 0; while (n) { n /= i; cnt += n; }
因此，直接將i換成5，就可以得到因子5的數(shù)量，也即n!末尾0的數(shù)量。
(3)。 返回階乘左邊的第二個(gè)數(shù)字
簡(jiǎn)單算法：用實(shí)數(shù)乘，超過(guò)100就除以10，最后取個(gè)位即可。因?yàn)檎麛?shù)部分的個(gè)位就是階乘結(jié)果左邊的第二個(gè)數(shù)字。相關(guān)題目： www.yzyedu.com
(4)。 判斷數(shù)值 m 是否可以整除 n!
算法：使用素因子判斷法
A. 首先直接輸出兩種特殊情況：
m == 0 則 0肯定不會(huì)整除n!;
n >= m 則 m肯定可以整除n!;
B. 那么就只剩最后一種情況：m > n，我們從m的最小素因子取起，設(shè)素因子為i那么可以 求得m的素因子i的個(gè)數(shù) nums1;再檢查閉區(qū)間 i ~ n 之間的數(shù)，一共包含多少個(gè)素因子i，就可以簡(jiǎn)單的利用上面(2)中所介紹的數(shù)學(xué)公式進(jìn)行計(jì)算得到nums2。如果nums2 < nums1，就表示1 ~ n中包含素因子的數(shù)量 < 除數(shù)m包含素因子i的數(shù)量，那么m必然不能整除n!，置ok = false。 www.yzjxsp.com
C. 最后：如果 !ok or m > n or m == 0 則不能整除;否則可以整除
(5)。數(shù)字N能否表示成若干個(gè)不相同的階乘的和：
這里可以選擇的階乘為：0! ~ 9!，實(shí)際上這一題與數(shù)論無(wú)關(guān)，與搜索有關(guān)。相關(guān)題目：http://acm.zju.edu.cn 的2358題。
分析，由于可供選擇的階乘數(shù)量較少，直接可以利用DFS搜索來(lái)做：
A. 首先將0 ~ 9的階乘作一個(gè)表A[10];再設(shè)置一個(gè)可以組成“和”的數(shù)組ans[N]。
B. 深度優(yōu)先搜索方法：
search(n) {
for(i = n; i <= 9; i++) {
sum += A[i]; //求和
如果sum在ans數(shù)組中不存在，則將sum插入到ans[]數(shù)組中
search(n+1);
sum -= A[i]; //回溯
}
}
C. 最后對(duì)于輸入n，就在ans數(shù)組中查找是否存在n，如果存在，則表示n可以表示成不同的階乘和，否則不行。