Baidu和EMC的筆勢題：對任意輸入的正整數(shù)N，編寫C程序求N!的尾部連續(xù)0的個(gè)數(shù)，并指出計(jì)算復(fù)雜度。如：18！＝6402373705728000，尾部連續(xù)0的個(gè)數(shù)是3。（不用考慮數(shù)值超出計(jì)算機(jī)整數(shù)界限的問題）

思路分析：

本題要用數(shù)學(xué)的方法來解決效率最高，連續(xù)K個(gè)0，則說明是10^K的倍數(shù)，即(2×5)^ K= 2^K× 5^K；待求的數(shù)為N*(N-1)(N-2)………1，由于每兩個(gè)數(shù)至少可以分解出1個(gè)2，2肯定比5多，因此K的個(gè)數(shù)取決于上式的分解因子中有幾個(gè)5的問題；能拆解出5的只可能是5的倍數(shù)，而能拆解出多少個(gè)5則看這個(gè)數(shù)是5的幾次方的倍數(shù)了

方法一：

int ZerosForN_1(int n)

{

int fives,result=0,i;

for(fives=5; n >=fives; fives+=5) // 循環(huán)次數(shù)為n/5

{

for(i=fives; i%5==0; i/=5) // 此處的最大循環(huán)次數(shù)為 LOG5(N)

{

++result;

}

}

//printf("%d/n",result);

return result;

}

for循環(huán)的算法復(fù)雜度最容易看出來，就是for循環(huán)的次數(shù)，最大循環(huán)次數(shù)為n/5 * LOG5(N) ，因此復(fù)雜度是O（nlogn）的

思路最清晰，即對于每個(gè)5的倍數(shù)的值，求其可被5整除的次數(shù)，即可求出最后5的因子個(gè)數(shù)和

方法二：

int ZerosForN_2(int n)

{

int pow5,result=0;

for(pow5=5; n >=pow5; pow5*=5) // 此處的循環(huán)次數(shù)為LOG5(N)

{

result+=n / pow5;

}

//printf("%d/n",result);

return result;

}

N不變，pow5以5的冪遞增，此算法的思想是求出N以內(nèi)所有被5整除的數(shù)的個(gè)數(shù)，所有被25整除的個(gè)數(shù)（在5的基礎(chǔ)上多出了一個(gè)5因子），所有被125整除的個(gè)數(shù)（在25的基礎(chǔ)上多出了一個(gè)5因子）。。。。

設(shè)最大數(shù)為N,
設(shè)5^(n+1)? > N? >= 5^n
[N/5] + [N/(5^2)] + [N/(5^3)] + ... + [N/(5^n)] 即為連續(xù)0的個(gè)數(shù)

上述式子的項(xiàng)數(shù)為log5(N)，即為循環(huán)的次數(shù)，故復(fù)雜度為log5(N)

方法三：

[N/5] + [N/(5^2)] + [N/(5^3)] + ... + [N/(5^n)]

=[N/5] + [[N/5]/5] + [ [[N/5]/5]/5] + ... + [。。。]

=A1+ [A1/5] + [A2/5] + ... + [An-1/5]

即上述各項(xiàng)構(gòu)成等比數(shù)列，An=An-1/5，等比為1/5

即對A1反復(fù)除5，只要其大于0，即相加，便得到以下算法：

int ZerosForN_3(int n)

{

int result=0;

n/=5; // A1

while(n >0)

{

result += n; //求和

n/=5; // 求An

}

//printf("%d/n",result);

return result;

}

等比數(shù)列的項(xiàng)數(shù)為log5(N)，即為循環(huán)的次數(shù)，故復(fù)雜度為log5(N)

總結(jié)

以上是生活随笔為你收集整理的N!的尾部连续0的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。