计算n阶乘中尾部零的个数

本来觉得问题挺容易的，不打算记录，谁知道一不小心，还真没做出来。最终凭借“朴实”的算法思想解决了问题，但是其中的曲折还真是汗颜。科学的思维指导确实必不可少，“野路子”的朴素的战斗理论不论是效率还是后续的算法演进都经不起考验。

这里只是记录一下自己最近两天对此问题的一些想法，目前只能说是解决了问题，并且满足题目要求。据说问题来自《编程之美》，以后刷书本的时候看到原题，如果需要补充的话，再来更新。

And，开始吧~

设计一个算法，计算出n阶乘中尾部零的个数 样例 11! = 39916800，因此应该返回 2 挑战 O(logN)的时间复杂度

先说结论，此问题大致有三种思路：第一种算出结果，然后查看末尾的0的个数，效果非常差；第二种，加法操作，从5开始，每次进5，然后判断，效果达不到O(logN)；第三种，每次除5，多次之后结束。 详情如下。

重点分析在算法2和算法3，需要的可以直接跳到这部分查看。

面对此问题，第一反应是直接计算结果：11!=39916800，然后设计程序判断末尾的0的个数，很简单就可以实现。 但是相应的会有很多的问题： 1、计算阶乘的开销 现在只是11的阶乘，都已经很大了，如果是5555550000000的阶乘呢？按照程序的计算结果，末尾会有1388887499996个0，计算开销很值得考虑。 2、溢出 按照上面的介绍，5555550000000的阶乘有1388887499996个0，那么可以推知阶乘的结果会是很大的一个整数，肯定会超出long类型的界限，结果会溢出。这样还要考虑处理溢出问题，又是另一个问题。 3、效率 算法2会涉及到效率问题，会发现即使是算法2也会出现计算时间超出要求的问题，那么更为“朴素”的算法1效率更是可想而知了。 因此，算法1，舍弃。

仔细的考虑问题，会发现末尾出现的0是10或10的倍数相乘的结果，而10其实是5与偶数相乘。也就是，最终结果中末尾出现的0是5、10、15、20、25…自身或与偶数相乘之后的产生的。下面可以分为偶数和5的倍数分析。

首先考虑偶数。 考虑2的幂次项2、4、8…中的2的个数，发现2的幂指数的增长速度远比5的幂指数增长的快，更不用说其他的普通偶数6、12、14…。因此可以认为有足够的偶数与奇数形式的5的倍数相乘产生足够的0。所以我们后面只考虑5的倍数。

接着考虑5的倍数。

其实1、2、3、4、6、7…都是可以不用考虑的，因此选择以5为迭代步数即可。 首先，这些数字都可以不用进行%5（对5取余数）运算，因此每次循环时可以直接将函数的count变量直接加1。其次，考虑25、125、625…等5的幂次项，因为他们每一个都可以在与偶数相乘之后产生多个0。因此，设置一个循环体，判断是多少幂次项，并将结果加进count。 综上所述，可以编写代码如下：

因为11不超过int类型的最大长度，所以并不会报错。但是如果是5555550000000，则会报错:

将数值进行强制类型转换也不行：long inNum=(long)5555550000000;。 一种解决方法是使用Scanner直接读取数值。 改进后的代码如下：

这时输入5555550000000则不会报错。 另外，如果需要的话，可使用System.currentTimeMillis();观察代码执行时间。

从最终的代码来看，问题是挺简单的。之所以折腾这么久都没有切入要害，直接做到真正的时间复杂度为O(logN)的效果，个人觉得是因为从分析题目的时候就没有真正理解O(logN)的真正含义。 类似于二叉搜索树，从根节点开始比较，比根节点小则与左子树比较，比根节点大则与右子树比较，相等或到达叶子节点则退出。如此循环迭代。 每次判断后，下一次可搜索的数据量均为上一次的1/2，如此循环复杂度为O(logN)。

遇到错误和不足就要反思，吸取教训。正视自己的缺点。

下面是个人吐槽时间，吃瓜子的观众可以有序退场了。

应该来讲，本题的最终目的是要做到O(logN)。分析题目的时候从O(logN)着手分析可能会是更好的方法。从科学的、有章可循的理论出发，作为指导思想，结合之前的例子（二叉搜索树），举一反三，解决本问题不是难事。 但是反过来，采用“朴素”方法，依靠个人经验，观察算法规律，然后解决问题。一个不行再去观察思考尝试下一种方法，虽然也是一种解决问题的思路，但如果想要在此基础上做到有章可循的逐步演进，怕是困难得多。 更何况如果观察不出规律呢？

先分析理论然后落实到实践，还是先动手做，再结合/总结升华出理论，值得推敲。 理性思考有助于身体健康，切记切记。与君共勉。