千萬不要被階乘嚇倒
更新時間：2013年05月23日 17:57:36 作者：
本篇文章是對階乘進行了詳細的分析介紹，需要的朋友參考下
階乘（Factorial）是個很有意思的函數，但是不少人都比較怕它，我們來看看兩個與階乘相關的問題：
1、 給定一個整數N，那么N的階乘N！末尾有多少個0呢？例如：N＝10，N?。? 628 800，N！的末尾有兩個0。
2、求N！的二進制表示中最低位1的位置。
有些人碰到這樣的題目會想：是不是要完整計算出N！的值？如果溢出怎么辦？事實上，如果我們從"哪些數相乘能得到10"這個角度來考慮，問題就變得簡單了。
首先考慮，如果N！= K×10^M，且K不能被10整除，那么N！末尾有M個0。再考慮對N！進行質因數分解，N！=（2^x）×（3^y）×（5^z）…，由于10 = 2×5，所以M只跟X和Z相關，每一對2和5相乘可以得到一個10，于是M = min（X, Z）。不難看出X大于等于Z，因為能被2整除的數出現(xiàn)的頻率比能被5整除的數高得多，所以把公式簡化為M = Z。
根據上面的分析，只要計算出Z的值，就可以得到N！末尾0的個數。
【問題1的解法一】
要計算Z，最直接的方法，就是計算i（i =1, 2, …, N）的因式分解中5的指數，然后求和：
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //統(tǒng)計N的階乘中那些能夠被5整除的因子的個數
j /= 5;
}
}
【問題1的解法二】
公式：Z = [N/5] +[N/5^2] +[N/5^3] + …（不用擔心這會是一個無窮的運算，因為總存在一個K，使得5^K > N，[N/5^K]=0。）
公式中，[N/5]表示不大于N的數中5的倍數貢獻一個5，[N/5^2]表示不大于N的數中5^2的倍數再貢獻一個5，……代碼如下：
ret = 0;
while(N)
{
ret += N / 5;
N /= 5;
}
問題2要求的是N！的二進制表示中最低位1的位置。給定一個整數N，求N！二進制表示的最低位1在第幾位？例如：給定N = 3，N！= 6，那么N！的二進制表示（1 010）的最低位1在第二位。
為了得到更好的解法，首先要對題目進行一下轉化。
首先來看一下一個二進制數除以2的計算過程和結果是怎樣的。
把一個二進制數除以2，實際過程如下：
判斷最后一個二進制位是否為0，若為0，則將此二進制數右移一位，即為商值（為什么）；反之，若為1，則說明這個二進制數是奇數，無法被2整除（這又是為什么）。
所以，這個問題實際上等同于求N！含有質因數2的個數+1。即答案等于N！含有質因數2的個數加1。 實際上N！都為偶數，因為質因數里面都有一個2，除了1以外，因為1的階乘是1，是個奇數，其他數的階乘都是偶數。。
【問題2的解法一】
由于N! 中含有質因數2的個數，等于 N/2 + N/4 + N/8 + N/16 + …[1]，
根據上述分析，得到具體算法，如下所示：
/*
可以先求出N!中2的個數（因為每存在一個2，則在數的
最低位多1個0）。因此求1的最低位的位置即為N!中2的個數+1；
*/
int lowestOnePos(int n)
{
int ret = 0; //統(tǒng)計n!中含有質因數2的個數
while(n)
{
n >>= 1;
ret += n;
}
return ret+1;
}
【問題2的解法二】
N！含有質因數2的個數，還等于N減去N的二進制表示中1的數目。我們還可以通過這個規(guī)律來求解。
下面對這個規(guī)律進行舉例說明，假設 N = 11011，那么N!中含有質因數2的個數為 N/2 + N/4 + N/8 + N/16 + …
即： 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二進制表示中1的個數
小結
任意一個長度為m的二進制數N可以表示為N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二進制數第i位上的數字（1或0）。所以，若最低位b[1]為1，則說明N為奇數；反之為偶數，將其除以2，即等于將整個二進制數向低位移一位。
相關題目
給定整數n，判斷它是否為2的方冪（解答提示：n>0&&（（n&（n-1））==0））。
--------------------------------------------------------------------------------
[1] 這個規(guī)律請讀者自己證明（提示N/k，等于1, 2, 3, …, N中能被k整除的數的個數）。
1、 給定一個整數N，那么N的階乘N！末尾有多少個0呢？例如：N＝10，N?。? 628 800，N！的末尾有兩個0。
2、求N！的二進制表示中最低位1的位置。
有些人碰到這樣的題目會想：是不是要完整計算出N！的值？如果溢出怎么辦？事實上，如果我們從"哪些數相乘能得到10"這個角度來考慮，問題就變得簡單了。
首先考慮，如果N！= K×10^M，且K不能被10整除，那么N！末尾有M個0。再考慮對N！進行質因數分解，N！=（2^x）×（3^y）×（5^z）…，由于10 = 2×5，所以M只跟X和Z相關，每一對2和5相乘可以得到一個10，于是M = min（X, Z）。不難看出X大于等于Z，因為能被2整除的數出現(xiàn)的頻率比能被5整除的數高得多，所以把公式簡化為M = Z。
根據上面的分析，只要計算出Z的值，就可以得到N！末尾0的個數。
【問題1的解法一】
要計算Z，最直接的方法，就是計算i（i =1, 2, …, N）的因式分解中5的指數，然后求和：
復制代碼 代碼如下:
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //統(tǒng)計N的階乘中那些能夠被5整除的因子的個數
j /= 5;
}
}
【問題1的解法二】
公式：Z = [N/5] +[N/5^2] +[N/5^3] + …（不用擔心這會是一個無窮的運算，因為總存在一個K，使得5^K > N，[N/5^K]=0。）
公式中，[N/5]表示不大于N的數中5的倍數貢獻一個5，[N/5^2]表示不大于N的數中5^2的倍數再貢獻一個5，……代碼如下：
復制代碼 代碼如下:
ret = 0;
while(N)
{
ret += N / 5;
N /= 5;
}
問題2要求的是N！的二進制表示中最低位1的位置。給定一個整數N，求N！二進制表示的最低位1在第幾位？例如：給定N = 3，N！= 6，那么N！的二進制表示（1 010）的最低位1在第二位。
為了得到更好的解法，首先要對題目進行一下轉化。
首先來看一下一個二進制數除以2的計算過程和結果是怎樣的。
把一個二進制數除以2，實際過程如下：
判斷最后一個二進制位是否為0，若為0，則將此二進制數右移一位，即為商值（為什么）；反之，若為1，則說明這個二進制數是奇數，無法被2整除（這又是為什么）。
所以，這個問題實際上等同于求N！含有質因數2的個數+1。即答案等于N！含有質因數2的個數加1。 實際上N！都為偶數，因為質因數里面都有一個2，除了1以外，因為1的階乘是1，是個奇數，其他數的階乘都是偶數。。
【問題2的解法一】
由于N! 中含有質因數2的個數，等于 N/2 + N/4 + N/8 + N/16 + …[1]，
根據上述分析，得到具體算法，如下所示：
復制代碼 代碼如下:
/*
可以先求出N!中2的個數（因為每存在一個2，則在數的
最低位多1個0）。因此求1的最低位的位置即為N!中2的個數+1；
*/
int lowestOnePos(int n)
{
int ret = 0; //統(tǒng)計n!中含有質因數2的個數
while(n)
{
n >>= 1;
ret += n;
}
return ret+1;
}
【問題2的解法二】
N！含有質因數2的個數，還等于N減去N的二進制表示中1的數目。我們還可以通過這個規(guī)律來求解。
下面對這個規(guī)律進行舉例說明，假設 N = 11011，那么N!中含有質因數2的個數為 N/2 + N/4 + N/8 + N/16 + …
復制代碼 代碼如下:
即： 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二進制表示中1的個數
小結
任意一個長度為m的二進制數N可以表示為N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二進制數第i位上的數字（1或0）。所以，若最低位b[1]為1，則說明N為奇數；反之為偶數，將其除以2，即等于將整個二進制數向低位移一位。
相關題目
給定整數n，判斷它是否為2的方冪（解答提示：n>0&&（（n&（n-1））==0））。
--------------------------------------------------------------------------------
[1] 這個規(guī)律請讀者自己證明（提示N/k，等于1, 2, 3, …, N中能被k整除的數的個數）。
相關文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)歸并排序算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家詳細介紹了C++重載運算符實現(xiàn)分數加減乘除，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C++ 中的異常拋出和捕獲方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C++實現(xiàn)單鏈表按k值重新排序的方法,結合實例形式分析了C++單鏈表中按照給定值進行判斷與排序的相關操作技巧,需要的朋友可以參考下2017-05-05
本文給大家分享給大家的是C語言的字符串大小比較的函數，有需要的小伙伴可以參考下。2015-07-07
C++入門基礎篇的內容為C++的基本特性,只有在掌握C++的基本特性后,是進入后面類和對象學習的基礎,下面這篇文章主要給大家介紹了關于C++入門基礎之命名空間、輸入輸出和缺省參數的相關資料,需要的朋友可以參考下2023-01-01
這篇文章主要介紹了C++變量初始化形式及其默認初始值問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
本文主要介紹了C語言讀取寫入ini配置文件的方法實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
由于在 C 語言中 '\' 一般是轉義字符的起始標志，故在路徑中需要用兩個 '\' 表示路徑中目錄層次的間隔，也可以使用 '/' 作為路徑中的分隔符，本文重點給大家介紹用c語言簡單實現(xiàn)文件 r/w 操作方法，感興趣的朋友一起學習吧2021-05-05
本篇文章是對宏、內聯(lián)函數與普通函數的區(qū)別進行了詳細的分析介紹，需要的朋友參考下2013-05-05