[1]   算有幾位數

 

嚴格講起,這是個假大數問題。 

 

可用 斯特靈公式逼近,但拿到的是一個近似值。要細算的話推導如下。

n! = n * (n-1) * (n-2) * .... * 2 * 1 ,算位數取 log10,

log10(n!) = log10(  n * (n-1) * (n-2) * .... * 2 * 1  ) ,

log10(n!) = log10(n) + log10(n-1) + log10(n-2) + .... + log10(2) + log10(1) ,

最後結果出來再取 ceil 。

 

雖浮點數有誤差,但有效是 53 位數,應付到幾十萬階乘是絕對足夠 (速度變慢倒是真的)

 

[2]  精算值 - 暴力法

 

一樣用大數去做,先放上暴力法

 

Code Snippet
  1. // --------------------------------------
  2. // 精算 n! 之值, 傳回有幾位數 , slow
  3. int fact(int n, int * Big, int size)
  4. {
  5.     int i, j, dig=1, carry=0;
  6.     int mini, pwr, num;
  7.     
  8.     if(n<0) {Big[0]=0; return -1;}
  9.     else if(n==0 || n==1) {Big[0]=1; return 1;}
  10.     
  11.     Big[0] = 1;
  12.     for(i=2 ; i<=n; ++i){
  13.  
  14.         // 進行大數乘法
  15.         if(size < dig) mini = size;
  16.         else mini = dig;
  17.  
  18.         for(carry =j=0 ; j<mini; ++j) {
  19.             Big[j] = carry + Big[j] * i;
  20.             carry  = Big[j] / BIG_CAP;
  21.             Big[j]%=BIG_CAP;
  22.         }
  23.         // 調進位
  24.         while(carry && j<size){
  25.             Big[j] = carry % BIG_CAP;
  26.             carry /= BIG_CAP;
  27.             ++j;
  28.         }
  29.         dig=j;
  30.     }
  31.     // 計算有幾個位數
  32.     dig = (j-1)*BIG_LEN;
  33.     for(num=Big[j-1]; num ; num/=10) ++dig;
  34.     return dig;
  35. }

 

注意中間使用的 dig 計算,拿來加快乘法速度。試過,用萬進位可行。

 

[4]  精算值 - 質因數分解

 

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2,把每個數做質因數分解,得到,

10! = 2^8 * 3^4 * 5^2  * 7,接下來就好辦了。

 

找一個階乘的質因式分解,其實有技巧,但需要較大的空間(一般題目應該都算夠用,目前看過找較大的是上萬)。一開始最好先建質數表,可以普通篩法或線性篩法都行 ( 幾十萬以內都很快)。篩法得到質數為 {2,3,5,7} 接著...

(1) 一開始拿質數 2 出來,

    i = 1 , cnt = 0;
    i = i * 2 = 2 , 10 / 2 = 5 , cnt+=5, cnt=5
    i = i * 2 = 4 , 10 / 4 = 2 , cnt+=2, cnt=7
    i = i * 2 = 8 , 10 / 8 = 1, cnt+=1 , cnt=8

(2) 再拿出質數 3 出來

    i = 1 , cnt = 0;
    i = i * 3 = 3 , 10 / 3 = 3 , cnt+=3, cnt=3
    i = i * 3 = 9 , 10 / 9 = 1 , cnt+=1, cnt=4
    i = i * 3 = 27 , 結束

其他拿質數 5、質數 7 都一樣。另外可以額外處理地方是在質數 7 。

因為是 10!,10/2 = 5,而 7 > 5,故可以判定,7 一定只有一個,就是自己,其它的絕不可能再分解下去 (很簡單的數論應用而已)。換比較通用的講法是:在求 n 階乘,做上述動作時,只要做到 n/2 便可,其它大於 n/2 的全都乘上去就行了。

fast-power 有個地方要注意,由於出來的結果可能會 overflow,故建議最好事先判斷有沒有可能會 ov。沒 ov 的話用大數做 fast_power 有點浪費,有 ov 就一定得用大數做 fast-power。

再來是看想不想進一步優化。再以 10! 為例。10! = 2^8 * 3^4 * 5^2  * 7^1,考慮前兩項就好,(2^8) * (3^4) =  (6^4) * (2^4),效果略有所不同。拆法有很多種 (特別注意到這個例子的次方剛好是 8 4 2 1 ),考慮溢位、速度之間做取捨之衡量,要設計好不容易。其他的不再贅述。

 

[5] 判斷尾數有幾個零

 

這是個假大數問題。

要構成一個 0 ,一定要有 2/5 同時存在相乘,如 8 * 5 = 2*2*2 *5 ,只能取出 1 對 2/5 出來,所以只有一個零;又如 16 * 125 = 2^4 * 5^3,可以取出 3 對出來,所以尾數有 3 個零。

然後很明顯的一點是,[1,n] 裡面,可以被 2 分解的個數,一定比可以比 5 分解的個數還多。

再來是,像 25 可以再被多提一個 5 出來、125 又可以再多提一個 5 出來,所以最後就是在算有幾個數字可以被 5 / 25 / 125 / 625 / .... 分解,總合就是答案。

 

Code Snippet
  1. #include <stdio.h>
  2.  
  3. int fact_tail_zero(int n)
  4. {
  5.     int ret=0;
  6.     while(n/=5) ret+=n;
  7.     return ret;
  8. }
  9.  
  10. int main()
  11. {
  12.     int x;
  13.     while(scanf("%d", &x)==1)
  14.         printf("tail zero : %d\n", fact_tail_zero(x));
  15.     return 0;
  16. }

 

 [6] 其他假大數階乘問題

 

(1)  求 N! 最右邊第一個非零數字 O(logn)

(2)  N! 之二進位表示法中,最低位元 1 之位置 -> 其實就是在求 [1,N] 質因數含 2 的個數。

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()