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