问题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 阅读(1916)
评论(0) 编辑 收藏 引用 所属分类:
算法基础