Problem 623 500!，階乘

Problem 623 題目要求是要輸入一整數 n，輸出 n! (n 的階乘)。

此題難在不能直接輸入一個整數 n ，再接著算出答案。因為光是500階乘就有1135長度的數字，何況題目還有個假設說「輸入的 n 值應該是不會超過 1000。」，可想而知，1000階乘的數字有多長了吧(1000階乘有2568長度) !

再來，做這種相乘一定需要用到陣列，但如果每輸入一次 n 值就要重算一次，那就太花時間了，所以必須使用一個二維陣列來記錄每個階乘的結果，也就是說，1~1000階乘算一次就可以了，只要輸入 n 值，就可依其位置將結果列出來。

首先先定義最大長度以及陣列要儲存幾個結果：

#define MAXLEN 2569
#define MAXROW 1001
int Factorial[MAXROW][MAXLEN] = {0};

以下為此題重點程式碼：

Factorial[0][0] = 1, Factorial[1][0] = 1 ;
   for (i = 2; i < MAXROW; i ++)
       for (j = 0; j < MAXLEN; j++){
           Factorial[i][j] += Factorial[i - 1][j] * i;
           if (Factorial[i][j] >= 10)
               Factorial[i][j + 1] += Factorial[i][j] / 10, Factorial[i][j] %= 10;
       }

By David.K

p623題目連結
回ACM題庫目錄
回首頁