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

ゝ一世哀愁。 2022-06-01 09:36 216阅读 0赞

今天开始算法练习，刚开始感觉挺简单的一个题，怎么就让自己乱了手脚。

题目：  
**设计一个算法，计算n阶乘中尾部零的个数**  
结果：  
**11! = 39916800，因此应该返回 2**

--------------------

*  见到题目的第一反应就是，简单通俗易懂。
    
    一般思维就是，首先算出N的阶乘，然后我们再从其尾部进行数0，就OK。果真，我也就这样写了，但是测试代码并未通过，提示是，算法太复杂。是啊，一个本身阶乘算法复杂度就不低，得重新设计算法。

--------------------

最终解题思路：

*  我们发现，末尾零个数的统计，也就是对N阶乘的除以10的个数的统计，这可以算是一种，统计算法，但是我们还是没能避免阶乘的计算，所以进一步的分析。
 *  除以10，可以将10分解成5乘以2，这样，我们发现，（1）5及其5的倍数乘以所有偶数，它的末尾都会出现0，另外我们发现，（2）5的幂次方数与偶数的乘积，末尾出现0的个数是次方数；（3）5的末尾有零和5的数（形如50，75，100，125等数）与偶数乘积末尾也必然会出现超过两个0。
 *  所以，我们可以进行计算了，首先计算出（1，2，3，4，5，6，7，8，9，10……n）中能被5整除的个数count，循环步数是5。此步就是筛选了满足（1）的条件的数。（countOne=n/5）
 *  在countOne个数中包含了5的幂次方的数，所以我们继续筛选（2）中满足的数，我们发现会发现，（3）中的数均是幂次方数的倍数。（countTwo=cuntOne/5^i(i=1,2,3,5….整数)）。
 *  我们构造循环，当while(count?=0)，循环结束。这个时候我们将所有的count？及加起来就是我们所要的个数。

const getZeros = function (n) { 
            let count=0;
            let tmp=parseInt(n/5);
            while(tmp!==0){
                count+=tmp;
                tmp=parseInt(tmp/5);
            }
            return parseInt(count);
    }

以上是我最终代码，当然在做这道题的时候还遇到一些基本的编程语法问题。

*  在取整和做除法的时候一定要注意是否需要将其装换为Int类型。因为在js中和别的编程语言不同，别的语言可以直接声明其类型。
 *  编程的时候，首先要扔掉传统的解题思维，更进一步的去对题目讨论。降低算法复杂度。

--------------------

## **js数字处理方法** ##

**直接取整**

*  parseInt(number)  
    这是常用的取整方法，它不仅仅可以处理Number类型，还可以处理字符串类型  
    `let num=parseInt(2018west)//2018`
 *  ~~number  
    所有取整中最快的，位运算
 *  number^0
 *  number<<0

**计算取整**

*  四舍五入`Math.round(number)`
 *  向上取整`Math.ceil(number)`
 *  向下取整`Math.floor(number)`

[数字处理方法参考][Link 1]

[Link 1]: https://www.jianshu.com/p/a3202bc3f7a4