随笔-80  评论-24  文章-0  trackbacks-0
问题1,求N!的十进制表示中末尾0的个数。
直接求出N!不太现实,很容易溢出。这个问题比较容易想到的是,因为2X5=10,所以可以求N!含有的因子2和因子5的个数。可以这样表示N!=2x * 3y * 5z * 7a *...,在这个表达式中,我们容易得出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(Nlog5N),当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((Nlog5N)/5) ,当n=1000000000时,上面程序大概运行5s,较上一算法有所改进,不过复杂度没有质的飞跃,笼统来说还是O(NlogN)。那么怎么进一步降低复杂度呢?
下面的算法就需要好好考虑如下事实:
1-N这N个数中有N/5个数是5的倍数
1-N这N个数中有N/52个数是52的倍数
1-N这N个数中有N/53个数是53的倍数
...
这样就比较明了了,容易得到如下算法:

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理