問題1，求N!的十進(jìn)制表示中末尾0的個(gè)數(shù)。
直接求出N!不太現(xiàn)實(shí)，很容易溢出。這個(gè)問題比較容易想到的是，因?yàn)?X5=10，所以可以求N!含有的因子2和因子5的個(gè)數(shù)。可以這樣表示N!=2
x * 3
y * 5
z * 7
a *...，在這個(gè)表達(dá)式中，我們?nèi)菀椎贸鰔 > z，因此只需要計(jì)算N!中含有因子5的個(gè)數(shù)，進(jìn)而可以轉(zhuǎn)化成計(jì)算1-N這N個(gè)數(shù)含有因子5的個(gè)數(shù)之和，所以可以寫出代碼：
1 int factorial1(int n) {
2 int count = 0;
3 while (n) {
4 int m = n;
5 while (m > 0 && m % 5 == 0) {
6 count++;
7 m /= 5;
8 }
9 n--;
10 }
11 return count;
12 }
可以發(fā)現(xiàn)，上面的算法復(fù)雜度為O(Nlog
5N)，當(dāng)N比較大時(shí)比如N=1000000000時(shí)，上面算法需要大概11s的時(shí)間，仔細(xì)想想，發(fā)現(xiàn)上面其實(shí)判斷了很多不需要判斷的值，因?yàn)楹芏鄶?shù)根本就不能被5整除，但是依然在外層while循環(huán)中被計(jì)算，所以我們可以只計(jì)算能被5整除的數(shù)，算法如下：
1 int factorial2(int n) {
2 int count = 0;
3 n = (n / 5) * 5;
4 while (n > 0) {
5 int m = n;
6 while (m > 0 && m % 5 == 0) {
7 count++;
8 m /= 5;
9 }
10 n -= 5;
11 }
12 return count;
13 }
上面算法從比n小的最大的能被5整除的數(shù)開始計(jì)算，且每次計(jì)算的步長(zhǎng)為5，即跳過不是5的倍數(shù)的數(shù)，時(shí)間復(fù)雜度為O((Nlog
5N)/5) ，當(dāng)n=1000000000時(shí)，上面程序大概運(yùn)行5s，較上一算法有所改進(jìn)，不過復(fù)雜度沒有質(zhì)的飛躍，籠統(tǒng)來說還是O(NlogN)。那么怎么進(jìn)一步降低復(fù)雜度呢？
下面的算法就需要好好考慮如下事實(shí)：
1-N這N個(gè)數(shù)中有N/5個(gè)數(shù)是5的倍數(shù)
1-N這N個(gè)數(shù)中有N/5
2個(gè)數(shù)是5
2的倍數(shù)
1-N這N個(gè)數(shù)中有N/5
3個(gè)數(shù)是5
3的倍數(shù)
...
這樣就比較明了了，容易得到如下算法：
1 int factorial3(int n) {
2 int count = 0;
3 while (n > 0) {
4 n /= 5;
5 count += n;
6 }
7 return count;
8 }
上面的算法復(fù)雜度為O(log
5N)，對(duì)n=1000000000，上面算法只運(yùn)行了0.004s。
問題2，求N!的二進(jìn)制表示中末尾0的個(gè)數(shù)。
該問題和上面的問題其實(shí)非常相似，稍作轉(zhuǎn)化就成為求N!中2的因子數(shù)，這樣就可以用上面的算法來解決：
1 int factorial3(int n) {
2 int count = 0;
3 while (n > 0) {
4 n >>= 1;
5 count += n;
6 }
7 return count;
8 }
這兩個(gè)問題的難點(diǎn)在轉(zhuǎn)化成求5或者2因子的個(gè)數(shù)；并且善于深入挖掘問題，編碼降低復(fù)雜度。
posted on 2012-09-04 12:24
myjfm 閱讀(2012)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)