欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

歡迎來(lái)到入門(mén)教程網(wǎng)!

C語(yǔ)言

當(dāng)前位置:主頁(yè) > 軟件編程 > C語(yǔ)言 >

千萬(wàn)不要被階乘嚇倒

來(lái)源:本站原創(chuàng)|時(shí)間:2020-01-10|欄目:C語(yǔ)言|點(diǎ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ù),然后求和:

復(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;
 }
}

【問(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,……代碼如下:
復(fù)制代碼 代碼如下:

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ù)上述分析,得到具體算法,如下所示:
復(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;
}

【問(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 + …
復(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è)長(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

網(wǎng)頁(yè)制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語(yǔ)言數(shù)據(jù)庫(kù)服務(wù)器

如果侵犯了您的權(quán)利,請(qǐng)與我們聯(lián)系,我們將在24小時(shí)內(nèi)進(jìn)行處理、任何非本站因素導(dǎo)致的法律后果,本站均不負(fù)任何責(zé)任。

聯(lián)系QQ:835971066 | 郵箱:835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有