千萬(wàn)不要被階乘嚇倒
階乘(Factorial)是個(gè)很有意思的函數(shù),但是不少人都比較怕它,我們來(lái)看看兩個(gè)與階乘相關(guān)的問(wèn)題:
1、 給定一個(gè)整數(shù)N,那么N的階乘N!末尾有多少個(gè)0呢?例如:N=10,N!=3 628 800,N!的末尾有兩個(gè)0。
2、求N!的二進(jìn)制表示中最低位1的位置。
有些人碰到這樣的題目會(huì)想:是不是要完整計(jì)算出N!的值?如果溢出怎么辦?事實(shí)上,如果我們從"哪些數(shù)相乘能得到10"這個(gè)角度來(lái)考慮,問(wèn)題就變得簡(jiǎn)單了。
首先考慮,如果N!= K×10^M,且K不能被10整除,那么N!末尾有M個(gè)0。再考慮對(duì)N!進(jìn)行質(zhì)因數(shù)分解,N!=(2^x)×(3^y)×(5^z)…,由于10 = 2×5,所以M只跟X和Z相關(guān),每一對(duì)2和5相乘可以得到一個(gè)10,于是M = min(X, Z)。不難看出X大于等于Z,因?yàn)槟鼙?整除的數(shù)出現(xiàn)的頻率比能被5整除的數(shù)高得多,所以把公式簡(jiǎn)化為M = Z。
根據(jù)上面的分析,只要計(jì)算出Z的值,就可以得到N!末尾0的個(gè)數(shù)。
【問(wèn)題1的解法一】
要計(jì)算Z,最直接的方法,就是計(jì)算i(i =1, 2, …, N)的因式分解中5的指數(shù),然后求和:
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //統(tǒng)計(jì)N的階乘中那些能夠被5整除的因子的個(gè)數(shù)
j /= 5;
}
}
【問(wèn)題1的解法二】
公式:Z = [N/5] +[N/5^2] +[N/5^3] + …(不用擔(dān)心這會(huì)是一個(gè)無(wú)窮的運(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,……代碼如下:
ret = 0;
while(N)
{
ret += N / 5;
N /= 5;
}
問(wèn)題2要求的是N!的二進(jìn)制表示中最低位1的位置。給定一個(gè)整數(shù)N,求N!二進(jìn)制表示的最低位1在第幾位?例如:給定N = 3,N!= 6,那么N!的二進(jìn)制表示(1 010)的最低位1在第二位。
為了得到更好的解法,首先要對(duì)題目進(jìn)行一下轉(zhuǎn)化。
首先來(lái)看一下一個(gè)二進(jìn)制數(shù)除以2的計(jì)算過(guò)程和結(jié)果是怎樣的。
把一個(gè)二進(jìn)制數(shù)除以2,實(shí)際過(guò)程如下:
判斷最后一個(gè)二進(jìn)制位是否為0,若為0,則將此二進(jìn)制數(shù)右移一位,即為商值(為什么);反之,若為1,則說(shuō)明這個(gè)二進(jìn)制數(shù)是奇數(shù),無(wú)法被2整除(這又是為什么)。
所以,這個(gè)問(wèn)題實(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ù)。。
【問(wèn)題2的解法一】
由于N! 中含有質(zhì)因數(shù)2的個(gè)數(shù),等于 N/2 + N/4 + N/8 + N/16 + …[1],
根據(jù)上述分析,得到具體算法,如下所示:
/*
可以先求出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;
}
【問(wèn)題2的解法二】
N!含有質(zhì)因數(shù)2的個(gè)數(shù),還等于N減去N的二進(jìn)制表示中1的數(shù)目。我們還可以通過(guò)這個(gè)規(guī)律來(lái)求解。
下面對(duì)這個(gè)規(guī)律進(jìn)行舉例說(shuō)明,假設(shè) N = 11011,那么N!中含有質(zhì)因數(shù)2的個(gè)數(shù)為 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二進(jìn)制表示中1的個(gè)數(shù)
小結(jié)
任意一個(gè)長(zhǎng)度為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,則說(shuō)明N為奇數(shù);反之為偶數(shù),將其除以2,即等于將整個(gè)二進(jìn)制數(shù)向低位移一位。
相關(guān)題目
給定整數(shù)n,判斷它是否為2的方冪(解答提示:n>0&&((n&(n-1))==0))。
--------------------------------------------------------------------------------
[1] 這個(gè)規(guī)律請(qǐng)讀者自己證明(提示N/k,等于1, 2, 3, …, N中能被k整除的數(shù)的個(gè)數(shù))。
上一篇:深入理解C++中常見(jiàn)的關(guān)鍵字含義
欄 目:C語(yǔ)言
下一篇:HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用分析詳解
本文標(biāo)題:千萬(wàn)不要被階乘嚇倒
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/4540.html
您可能感興趣的文章
- 01-10C語(yǔ)言 解決不用+、-、&#215;、&#247;數(shù)字運(yùn)算符做加法
- 01-10深入分析父子線(xiàn)程、進(jìn)程終止順序不同產(chǎn)生的結(jié)果
- 01-10深入分析C中不安全的sprintf與strcpy
- 01-10探討編寫(xiě)int strlen(char *strDest);不允許定義變量的問(wèn)題
- 01-10C++虛析構(gòu)函數(shù)的使用分析
- 01-10解決不用sizeof求出int大小的方法
- 01-10為什么要學(xué)習(xí)C語(yǔ)言 C語(yǔ)言?xún)?yōu)勢(shì)分析
- 01-10C++用new創(chuàng)建對(duì)象和不用new創(chuàng)建對(duì)象的區(qū)別解析
- 01-10解析C++中不能重載為友元函數(shù)的四個(gè)運(yùn)算符
- 01-10關(guān)于c語(yǔ)言的一個(gè)小bug詳解


閱讀排行
- 1C語(yǔ)言 while語(yǔ)句的用法詳解
- 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹(shù)的示例代碼(圣誕
- 3利用C語(yǔ)言實(shí)現(xiàn)“百馬百擔(dān)”問(wèn)題方法
- 4C語(yǔ)言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
- 5c語(yǔ)言計(jì)算三角形面積代碼
- 6什么是 WSH(腳本宿主)的詳細(xì)解釋
- 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
- 8正則表達(dá)式匹配各種特殊字符
- 9C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
- 10C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
本欄相關(guān)
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用
- 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
- 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)
- 04-02c語(yǔ)言用函數(shù)寫(xiě)分段 用c語(yǔ)言表示分段
- 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)
- 04-02c語(yǔ)言編寫(xiě)函數(shù)冒泡排序 c語(yǔ)言冒泡排
- 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
- 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段
- 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎
- 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求
隨機(jī)閱讀
- 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
- 01-10C#中split用法實(shí)例總結(jié)
- 01-10SublimeText編譯C開(kāi)發(fā)環(huán)境設(shè)置
- 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能?
- 04-02jquery與jsp,用jquery
- 01-10delphi制作wav文件的方法
- 01-11Mac OSX 打開(kāi)原生自帶讀寫(xiě)NTFS功能(圖文
- 01-10使用C語(yǔ)言求解撲克牌的順子及n個(gè)骰子
- 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
- 01-11ajax實(shí)現(xiàn)頁(yè)面的局部加載