大數階乘的由來

　　　　一個正整數的階乘（Factorial）是所有小於及等於該數的正整數的積，並且0的階乘為1。自然數n的階乘寫作n!。亦即n!=1×2×3×...×(n-1)×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。 但是在求解數字較大的階乘時，由於階乘累乘的性質，導致結果過大，在C語言中，哪怕是double和Longlong都無法儲存過多的數位，而解決這個問題的辦法，最簡單的就是由數組來儲存。

大致思路

　　由於是超過了一個定義變數的最大範圍，所以使用數組解決，畢竟C語言中 int的範圍為-(2的31次方-1)到(2的31次方-1)，數字為-2 147 483 647~2 147 483 647。double的表示範圍為+1.111111111111111111111*2^1023(1.後面52個1)為1.7*10^308，看起來double型應該夠了的，可是，精度卻並不高，數值精度只有 15~16 位，就是說，一個 308 位長的浮點數，只有前 15～16 位的精度是可信和有保證的，超出部分就沒有精度可言了，而且，越靠後，就越不靠譜。而數組申請一個過萬的空間輕輕鬆松，每個空間再存int或double型數據，加在一起可以輸出的空間就可想而知了。

　　用數組解決該問題，簡單來說就是就是將大數的各個位置用取餘取出放在數組的連續空間上，然後逆序輸出。而其中需要註意的就是化繁為簡，分解成多個子問題進行計算（是不是有些耳熟），即在已經分佈好位置的n-1的數位上進行下一次的階乘，保證了每位相乘都是一個很小的數字去乘下一個階乘數。運用雙迴圈分別進行乘數的移動和每位數字與此時乘數的計算，最後輸出。下麵是代碼：

 1 #define N 10001
 2 int a[N];
 3 double arr[N];
 4 
 5 void  factorial1(int n)
 6 {
 7     a[0] = 1;
 8     int len = 1;
 9     int tmp, next;
10     for (int i = 1; i <= n; i++)
11     {
12         next = 0;
13         for (int j = 0; j < len; j++)
14         {
15             tmp = a[j] * i+next; //當前階乘值
16             a[j] = tmp % 10; //當前位置僅保留階乘值的最後一位
17             next = tmp / 10; //保存大於10的餘下階乘值，進行下一次存儲
18             if (j >= len - 1 && next > 0) //動態增加數組長度
19             {
20                 len++;          //當數組在最後一位且存在next值時，就增加一個長度進行下一次存儲。
21             }
22         }
23     }
24     for (int i = len-1; i >=0 ; i--)//倒敘輸出數組
25     {
26         printf("%d",a[i]);
27         if (i % 5 == 0&&i!=0)//分組輸出，每組5個
28             printf(",");
29     }
30 }

　　筆者前段時間剛結束對滾動數組和動態規劃的淺略總結，所以在開始便想用動態規劃解決，所以分析了一下最優化原理和無後效原則。

• 和斐波那契數列相同，因為相乘的數是固定且沒有其它因素影響的，所以符合最優化原理
• 前面的數列由於是固定數值，無法改變影響後面結果（比如乘到某個數時，前面的一個值要進行改變，導致該值後面一系列的數據都進行改變），所以符合無後效原則。

因此理論上來說是可以DP的，簡單來想，普通階乘可以DP嗎？當然可以（畢竟百度就能看見）。但如果這裡我們直接簡單的計算並輸出的話，數字過大時就會出現結果不准確，即：

 1 void factorial2(int n)
 2 {
 3     arr[1] = 1;
 4     arr[0] = 1;
 5     for (int i = 2; i <= n; i++)
 6     {
 7         arr[i] = arr[i - 1] * i;
 8     }
 9     printf("%lf\n", arr[n]);
10 }

　　在main函數中使用

int main()
{
    int n;//階乘位數
    double a;
    scanf("%d",&n);
    factorial1(n);
    printf("\n");
    printf("double:\n");
    factorial2(n);
    return 0;
}

　　輸出結果：

 　　可以看到 factorial2 函數輸出的內容是個 inf，而 factorial1 使用的數組輸出則完美的輸出了內容。而可不可以使用DP來解決大數的問題，筆者愚鈍，只是覺得行，在這裡未能解決。還請各位大佬看官如有想法，多多指教。

By the way，學個新單詞。