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