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