大家好，又見面了，我是你們的朋友全棧君。
優化階乘算法的探索
中國地質大學（武漢） 陳海豐
階乘(factorial)是基斯頓·卡曼(Christian Kramp, 1760 – 1826)于1808年發明的運算符号。階乘，也是數學裡的一種術語，是指從1乘以2乘以3乘以4一直乘到所要求的數。例如所要求的數是4，則階乘式是1×2×3×4，得到的積是24，24就是4的階乘。如果所要求的數是n，則階乘式是1×2×3×……×n，設得到的積是x，x就是n的階乘。在表示階乘時，就使用“！”來表示，如n階乘，就表示為n!。
根據階乘的定義，我們不難得到求解階乘的遞推式。
…………………………………(1)
當n值很小時，在計算機中可以直接用整型資料的運算就可以解決了，可是當n值很大，比如n＝10000時計算結果就不能用現有的資料類型來存放了，因為它的位數已遠遠超過了現有的資料類型（如10000！有35660位）。為了解決所有資料類型都無法存放這樣一個龐大的資料，目前大家采用的是将一個大數一位一位的存放到一個字元型數組或整型數組中，然後要運算時對其每一位進行單獨運算，這樣就解決了龐大資料的存放問題。但具體怎樣對兩個都比較大的數的作乘法運算呢？這就要利用大整數的高精度運算。如A,B都是位數比較多的大整數，現在要作A*B運算。國小時我們作45*12是先把12中的2與45的個位5相乘，再把2與45的十位4相乘，然後同樣再把12中的1與45中的每一位從低到高依次相乘。在這裡我們也可以模拟45*12，把A中每一位從低到高與B中的個位相乘，與後再與B中的十位相乘，依次類推，最後把所有的結果對應相加就可以得到所要求的結果了。
具體代碼（一）：
#include <stdio.h>
#include <string.h>
char a[40000], b[10];
int c[40000];
int main()
{
int n;
while(scanf(“%d”, &n) != EOF){
int la, lb, lc, i, j, k, k1;
if(n == 0 || n == 1){
printf(“1/n”);
continue;
} //幾種特殊情況
if(n == 2){
printf(“2/n”);
continue;
}
a[0] = 50; //初始化使是最先相乘的數從開始
for(k1 = 3;k1 <= n;k1++){
k = k1;
for(j = 0;k;j++){
b[j] = k % 10 + 48;
k /= 10;
}
la = strlen(a);
lb = strlen(b);
memset(c, 0, sizeof(c));
for(i = 0;i < la;i++){
for(j = 0;j < lb;j++){
c[i + j] += (a[i] – 48) * (b[j] – 48);
//循環相乘，結果存放到另一數組中
c[i + j + 1] += c[i + j] / 10; //進位
c[i + j] %= 10;
lc = i + j + 1; //目前位
}
}
if(c[lc] == 0) lc–;
for(i = lc;i >= 0;i–)
for(i = lc;i >= 0;i–) a[i] = c[i] + 48;
//将結果複制到數組a中，再和b數組相乘
}
for(i = lc;i >= 0;i–){ //輸出結果時從數組的最後一個開始輸出
printf(“%c”, a[i]);
}
printf(“/n”);
memset(a, 0, sizeof(a)); //将數組全部初始化
memset(b, 0, sizeof(b));
}
return 0;
}
上面程式可以計算大數的階乘，但是效率非常的低，如10000！的階乘需要2000Ms左右，是以這種算法并不能解決實際問題。考慮到上面的程式是一位一位的把一個大數存放下來，然後相乘時也是一位一位的進行的。然後我想到定義一個整型的數組，每一位不是存放一位而是存放五位，這樣相加，相乘的次數就是原來的 ，10000！運算時間是200Ms，是原來的 。
具體代碼（二）：
#include<stdio.h>
int main()
{
int n;
printf(“請輸入一個整數N(0~20000)：/n”);
while(scanf(“%d”, &n) != EOF){
int s[16000] = {0}, j, i, k = 0, t = 0, p = 0;
long sum = 0;
s[0] = 1;
for(j = 1;j <= n;j++){
for(i = 0;i <= t;i++){
sum = s[i] * j + p;
p = 0;
if(sum > 99999){
s[i] = sum % 100000; //每一位存放位
p = sum / 100000;
if(t == i){
t++;
s[t] = 0;
}
}
else s[i]=sum;
}
}
printf(“%d!=”, n);
printf(“%d”, s[t]);
for(i = t – 1;i >= 0;i–){
printf(“%05d”,s[i]);
}
printf(“/n/n”);
printf(“請再輸入一個整數N(0~20000)：/n”);
}
return 0;
}
當然在程式中可以把存放大數的數組定義成長整型（long）則每一個數組元素可以存放更多位，10000！的運作時間可以縮短到50Ms。在實踐中算法的可行性是非常重要的，算法要不斷的優化才能有機實際作用，是以要學會優化算法，提高自己的程式設計能力。
本文來自CSDN部落格，轉載請标明出處：http://blog.csdn.net/cschf/archive/2008/05/28/2491623.aspx
釋出者：全棧程式員棧長，轉載請注明出處：https://javaforall.cn/164010.html原文連結：https://javaforall.cn