千萬不要被階乘嚇倒

2020-01-26 16:10:22

字體：大中小

供稿：網(wǎng)友

階乘（Factorial）是個(gè)很有意思的函數(shù)，但是不少人都比較怕它，我們來看看兩個(gè)與階乘相關(guān)的問題：
1、給定一個(gè)整數(shù)N，那么N的階乘N！末尾有多少個(gè)0呢？例如：N＝10，N?。? 628 800，N！的末尾有兩個(gè)0。
2、求N！的二進(jìn)制表示中最低位1的位置。
有些人碰到這樣的題目會想：是不是要完整計(jì)算出N！的值？如果溢出怎么辦？事實(shí)上，如果我們從"哪些數(shù)相乘能得到10"這個(gè)角度來考慮，問題就變得簡單了。
首先考慮，如果N！= K×10^M，且K不能被10整除，那么N！末尾有M個(gè)0。再考慮對N！進(jìn)行質(zhì)因數(shù)分解，N！=（2^x）×（3^y）×（5^z）…，由于10 = 2×5，所以M只跟X和Z相關(guān)，每一對2和5相乘可以得到一個(gè)10，于是M = min（X, Z）。不難看出X大于等于Z，因?yàn)槟鼙?整除的數(shù)出現(xiàn)的頻率比能被5整除的數(shù)高得多，所以把公式簡化為M = Z。
根據(jù)上面的分析，只要計(jì)算出Z的值，就可以得到N！末尾0的個(gè)數(shù)。
【問題1的解法一】
要計(jì)算Z，最直接的方法，就是計(jì)算i（i =1, 2, …, N）的因式分解中5的指數(shù)，然后求和：

復(fù)制代碼代碼如下:

ret = 0; 
for(i = 1; i <= N; i++) 
{ 
 j = i; 
 while(j % 5 ==0) 
 { 
  ret++;     //統(tǒng)計(jì)N的階乘中那些能夠被5整除的因子的個(gè)數(shù)
  j /= 5; 
 }
}

【問題1的解法二】
公式：Z = [N/5] +[N/5^2] +[N/5^3] + …（不用擔(dān)心這會是一個(gè)無窮的運(yùn)算，因?yàn)榭偞嬖谝粋€(gè)K，使得5^K > N，[N/5^K]=0。）
公式中，[N/5]表示不大于N的數(shù)中5的倍數(shù)貢獻(xiàn)一個(gè)5，[N/5^2]表示不大于N的數(shù)中5^2的倍數(shù)再貢獻(xiàn)一個(gè)5，……代碼如下：

復(fù)制代碼代碼如下:

ret = 0; 
while(N) 
{
 ret += N / 5; 
 N /= 5;
}

問題2要求的是N！的二進(jìn)制表示中最低位1的位置。給定一個(gè)整數(shù)N，求N！二進(jìn)制表示的最低位1在第幾位？例如：給定N = 3，N！= 6，那么N！的二進(jìn)制表示（1 010）的最低位1在第二位。
為了得到更好的解法，首先要對題目進(jìn)行一下轉(zhuǎn)化。
首先來看一下一個(gè)二進(jìn)制數(shù)除以2的計(jì)算過程和結(jié)果是怎樣的。
把一個(gè)二進(jìn)制數(shù)除以2，實(shí)際過程如下：
判斷最后一個(gè)二進(jìn)制位是否為0，若為0，則將此二進(jìn)制數(shù)右移一位，即為商值（為什么）；反之，若為1，則說明這個(gè)二進(jìn)制數(shù)是奇數(shù)，無法被2整除（這又是為什么）。
所以，這個(gè)問題實(shí)際上等同于求N！含有質(zhì)因數(shù)2的個(gè)數(shù)+1。即答案等于N！含有質(zhì)因數(shù)2的個(gè)數(shù)加1。實(shí)際上N！都為偶數(shù)，因?yàn)橘|(zhì)因數(shù)里面都有一個(gè)2，除了1以外，因?yàn)?的階乘是1，是個(gè)奇數(shù)，其他數(shù)的階乘都是偶數(shù)。。
【問題2的解法一】
由于N! 中含有質(zhì)因數(shù)2的個(gè)數(shù)，等于 N/2 + N/4 + N/8 + N/16 + …[1]，
根據(jù)上述分析，得到具體算法，如下所示：

復(fù)制代碼代碼如下:

/*
可以先求出N!中2的個(gè)數(shù)（因?yàn)槊看嬖谝粋€(gè)2，則在數(shù)的 
最低位多1個(gè)0）。因此求1的最低位的位置即為N!中2的個(gè)數(shù)+1； 
*/
int lowestOnePos(int n) 
{ 
    int ret = 0;     //統(tǒng)計(jì)n!中含有質(zhì)因數(shù)2的個(gè)數(shù)
    while(n) 
    { 
        n >>= 1; 
        ret += n; 
    } 
    return ret+1;
}

【問題2的解法二】
N！含有質(zhì)因數(shù)2的個(gè)數(shù)，還等于N減去N的二進(jìn)制表示中1的數(shù)目。我們還可以通過這個(gè)規(guī)律來求解。
下面對這個(gè)規(guī)律進(jìn)行舉例說明，假設(shè) N = 11011，那么N!中含有質(zhì)因數(shù)2的個(gè)數(shù)為 N/2 + N/4 + N/8 + N/16 + …

復(fù)制代碼代碼如下:

即： 1101 + 110 + 11 + 1 
=（1000 + 100 + 1） 
+（100 + 10） 
+（10 + 1） 
+ 1 
=（1000 + 100+ 10 + 1）+（100 + 10 + 1）+ 1 
= 1111 + 111 + 1 
=（10000 -1）+（1000 - 1）+（10-1）+（1-1） 
= 11011-N二進(jìn)制表示中1的個(gè)數(shù) 

小結(jié)
任意一個(gè)長度為m的二進(jìn)制數(shù)N可以表示為N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二進(jìn)制數(shù)第i位上的數(shù)字（1或0）。所以，若最低位b[1]為1，則說明N為奇數(shù)；反之為偶數(shù)，將其除以2，即等于將整個(gè)二進(jìn)制數(shù)向低位移一位。
相關(guān)題目
給定整數(shù)n，判斷它是否為2的方冪（解答提示：n>0&&（（n&（n-1））==0））。
--------------------------------------------------------------------------------
[1] 這個(gè)規(guī)律請讀者自己證明（提示N/k，等于1, 2, 3, …, N中能被k整除的數(shù)的個(gè)數(shù)）。

上一篇：最長公共子字符串的使用分析

下一篇：求子數(shù)組最大和的解決方法詳解