阶乘算法之一N! 末尾有多少个零 - 跑龙套@程序 - ITeye技术网站
博客分类：
题：给定一个整数N，求出N!末尾有多少个零，比如N=10，N!=3628800，10！末尾有两个零。
首先温固一下阶乘的相关知识！
阶乘(factorial)是基斯顿·卡曼(Christian Kramp, 1760 – 1826)于1808年发明的运算符号。阶乘，也是数学里的一种术语。
任何大于1的自然数n阶乘表示方法：n!=1×2×3×……×n 或n!= n×(n-1)!
0！=1，注意(0的阶乘是存在的).
当n为奇数时表示不大于n的所有奇数的乘积 如：7!!=1×3×5×7
当n为偶数时表示不大于n的所有偶数的乘积(除0外） 如：8!!=2×4×6×8
小于0的整数-n的阶乘表示：
（-n）！= 1 / (n+1)!
双阶乘是怎么提出来的，是根据阶乘推导出来的吗？这点百思不解？
然后理一下本题的解题思路：
N个自然数相乘，结尾0的个数，依赖有多少个10相乘（有两个10相乘，结尾0的个数就为2），10=2×5，则可以理解为结尾0的个数依赖因子中2的个数和5的个数，而对于连续的自然数来说，2出现的频率比5高的多，所以最终只需要计算出因子中5的个数，即为答案。
把想法整理为JAVA代码，如下所示：
解题思路一：分析阶乘因子中的每一个数，计算其包含5的个数，最后求总和
private int zeroNum(int n){
int ret = 0;
for(int i=1;i&=n;i++){
while(j%5 == 0){
时间复杂度为：Nlog5N
解题思路二：
令f(x)表示正整数x末尾所含有的“0”的个数，则有：
当0 & n & 5时，f(n!) = 0;
当n &= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）
下面对这个结论进行证明：
(1) 当n & 5时, 结论显然成立。
(2) 当n &= 5时，令n！= （5k * 5(k-1) * ... * 10 * 5） * a，其中 n = 5k + r (0 &= r &= 4)，a是一个不含因子“5”的整数。
对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 &= i &= k)，都含有因子“5”，并且在区间 [5(i-1), 5i] (1 &= i &= k)内存在偶数，也就是说，a中存在一个因子“2”与5i相对应。即，这里的k个因子“5”与 n！末尾的k个“0”一一对应。
n！= （5k * 5(k-1) * ... * 10 * 5） * a = (5k * k!) *a
令f(x)表示正整数x末尾所含有的“0”的个数, g(x)表示正整数x的因式分解中因子“5”的个数，则利用上面的的结论有：
f(n!) = g(n!) = g(5k * k!* a) =g(5k * k!)= k + g(k!) = k + f(k!)
所以，最终的计算公式为：
当0 & n & 5时，f(n!) = 0;
当n &= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。
public int method02(int n){
int ret = 0;
int k = n/5;
return k + method02(k);
时间复杂度为：log5N
解题思路三：
乘积末尾的0的个数依赖于因子中的2的个数和5的个数。对于阶乘来说，每2个数字就至少有一个2的因子，所以2的因子是足够的。5的因子相对少些，至少连续5个数才能保证一定出现一个。注意，这里连续5个书保证出现一个5的因子是指最少的情况。比如1，2，3，4，5，这就只会出现一个。但是考虑 21，22，23，24，25，25 = 5 * 5,所以如果乘以25那就能得到2个5的因子。依次会有3个5的因子…
所以n!中5的个数的计算是：[n/5]+[n/(5*5)]+[n/(5*5*5)]+....
public int method03(int n){
int ret = 0;
int baseNum = 5;
while (n &= baseNum)
ret += n/baseN
baseNum *= 5;
时间复杂度为：log5N
对于解法二和解法三，我这里写的时间复杂度都为log5N
,但实际验证，解法三比解法二更高效，所以不知道是否时间复杂度写的有问题？高人求解！！！
后记（顿悟）：
算法三之所以优于算法二，因为算法二是用到递归算法，递归一系列的函数调用，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。所以算法三在时间复杂度和空间复杂度上是优于算法二的。
参考资料：
《编程之美》
浏览: 111584 次
来自: 上海
我怎么没看出多线程啊，就单线程再跑嘛
多线程 不错
liujiafei_2007 写道你好，问个问题，取钱时不用判 ...
你好，问个问题，取钱时不用判断取出的金额是否大于账户的余额吗？ ...
liubey 写道User 怎么会持有一个Toilet 呢上厕 ...高数中两个阶乘号什么意思？_考研吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：2,010,234贴子：
高数中两个阶乘号什么意思？收藏
高手指点一下！
考研,每天2.6小时,高效备考18考研,直播+录播,直达高分,更可免息分期付款!考研新东方在线,87%考研在线市场占有率,犀利名师,倾情助阵!
就是阶乘的阶乘。
好像都是隔一项相乘！例如9！！就是9×7×5×3×1 正解！！
擦，我一直以为是阶乘的阶乘，变的好大的样子，难怪老觉得 书上那个sinx^n 的积分公式 不怎么对，原来是！！理解问题
怎么没遇到过这个。。
碉了堡了，目前没注意到额
n为偶数，偶数相乘，为奇数，奇数相乘
比如4!! 4*2. 7!!等于7*5*3*1
我一直以为是奇数的阶乘，，原来还有偶数的。。
昨天我也在全书上看到了……那个化简得到的（2n-1）!!一开始愣了下，原来可以这样写……
提供全日制学士及硕士课程,師資優秀,专业热门,就业率高!
每项相差二
详解：若n是偶数，例如8！！=8x6x4x2x（兀／2），若n是奇数，例如9！！＝9X7X5x3x．即每每隔2乘一次，是偶数最后还要乘以兀／2.
楼主不解还可以问！
。。。这我们教材上就有。。。。
永乐大帝的书里出现了。。。。
就是不超过这个数，并且与这个数相同奇偶性的数的连乘
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或后使用快捷导航没有帐号？
查看: 1143|回复: 3
如何用阶乘的方法表示奇数的连乘？
中级战友, 积分 2306, 距离下一级还需 694 积分
K币2294 元
在线时间805 小时
主题帖子积分
中级战友, 积分 2306, 距离下一级还需 694 积分
中级战友, 积分 2306, 距离下一级还需 694 积分
K币2294 元
比如1*3*5*7*9*.....*2n+1&&怎么用阶乘的形式表示出来啊，大神求解
一般战友, 积分 171, 距离下一级还需 329 积分
在线时间4 小时
主题帖子积分
一般战友, 积分 171, 距离下一级还需 329 积分
一般战友, 积分 171, 距离下一级还需 329 积分
中级战友, 积分 2306, 距离下一级还需 694 积分
K币2294 元
在线时间805 小时
主题帖子积分
中级战友, 积分 2306, 距离下一级还需 694 积分
中级战友, 积分 2306, 距离下一级还需 694 积分
K币2294 元
ZemhH 发表于
如果不是用双阶乘呢？单阶乘怎么表示？
一般战友, 积分 171, 距离下一级还需 329 积分
在线时间4 小时
主题帖子积分
一般战友, 积分 171, 距离下一级还需 329 积分
一般战友, 积分 171, 距离下一级还需 329 积分
课程预告，帮学堂出品
没有这种表示
您还剩5次免费下载资料的机会哦~
扫描二维码下载资料
使用手机端考研帮，进入扫一扫在“我”中打开扫一扫，扫描二维码下载资料
Powered by Discuz!计算n阶乘中尾部零的个数-爱编程
计算n阶乘中尾部零的个数
本来觉得问题挺容易的，不打算记录，谁知道一不小心，还真没做出来。最终凭借“朴实”的算法思想解决了问题，但是其中的曲折还真是汗颜。科学的思维指导确实必不可少，“野路子”的朴素的战斗理论不论是效率还是后续的算法演进都经不起考验。
这里只是记录一下自己最近两天对此问题的一些想法，目前只能说是解决了问题，并且满足题目要求。据说问题来自《编程之美》，以后刷书本的时候看到原题，如果需要补充的话，再来更新。
And，开始吧~
设计一个算法，计算出n阶乘中尾部零的个数
11! = ，因此应该返回 2
O(logN)的时间复杂度
先说结论，此问题大致有三种思路：第一种算出结果，然后查看末尾的0的个数，效果非常差；第二种，加法操作，从5开始，每次进5，然后判断，效果达不到O(logN)；第三种，每次除5，多次之后结束。
详情如下。
重点分析在算法2和算法3，需要的可以直接跳到这部分查看。
算法1：最朴素
面对此问题，第一反应是直接计算结果：11!=，然后设计程序判断末尾的0的个数，很简单就可以实现。
但是相应的会有很多的问题：
1、计算阶乘的开销
现在只是11的阶乘，都已经很大了，如果是0的阶乘呢？按照程序的计算结果，末尾会有6个0，计算开销很值得考虑。
按照上面的介绍，0的阶乘有6个0，那么可以推知阶乘的结果会是很大的一个整数，肯定会超出long类型的界限，结果会溢出。这样还要考虑处理溢出问题，又是另一个问题。
算法2会涉及到效率问题，会发现即使是算法2也会出现计算时间超出要求的问题，那么更为“朴素”的算法1效率更是可想而知了。
因此，算法1，舍弃。
算法2：以5为迭代步数
仔细的考虑问题，会发现末尾出现的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、5、6、7、8、9、10、11...
其实1、2、3、4、6、7…都是可以不用考虑的，因此选择以5为迭代步数即可。
首先，这些数字都可以不用进行%5（对5取余数）运算，因此每次循环时可以直接将函数的count变量直接加1。其次，考虑25、125、625…等5的幂次项，因为他们每一个都可以在与偶数相乘之后产生多个0。因此，设置一个循环体，判断是多少幂次项，并将结果加进count。
综上所述，可以编写代码如下：
public class Solution {
public long trailingZeros(long n) {
long count = 0;
long pwr = 25;
for (long temp = 5; temp &= temp+=5) {
while (temp % pwr == 0) {
代码很简单，不再解释。
但是效率很差，分析发现代码的时间复杂度实际是O(N/5)~=O(N)，达不到要求的O(logN)。
算法2虽然可以解决问题，但考虑执行效率，算法2应该舍弃。
算法3：科学思想
这个算法真的是感触很深，对平时很多习以为常的公式、道理有了非常直观的认识，因此对自己的冲击很大，也促进了思考的进步。
提交算法2的代码，发现前面的简单测试都能通过，但是数值0测试失败。特别是实现了时间复杂度O(logN)的算法3之后，才发现两者时间开销差别真的是很大。
1、2、3、4、5、6、7、8、9、10、11、...
1、分析上面的数列可知，每5个数中会出现一个可以产生结果中0的数字。把这些数字抽取出来是：
...、5、...、10、...、15、...、20、...、25、...
这些数字其实是都能满足5*k的数字，是5的倍数。统计一下他们的数量：n1=N/5。比如如果是101，则101之前应该是5,10,15,20,...,95,100共101/5=20个数字满足要求。
整除操作满足上面的数量统计要求。
2、将1中的这些数字化成5*(1、2、3、4、5、...)的形式，内部的1、2、3、4、5、...又满足上面的分析：每5个数字有一个是5的倍数。抽取为：
...、25、...、50、...、75、...、100、...、125、...
而这些数字都是25的倍数（5的2次幂的倍数），自然也都满足5*k的要求。
这些数字是25、50、75、100、125、...=5*(5、10、15、20、25、...)=5*5*(1、2、3、4、5、...)，内部的1、2、3、4、5、...又满足上面的分析，因此后续的操作重复上述步骤即可。
统计一下第二次中满足条件的数字数量：n2=N/5/5，101/25=(101/5)/5=4。
因为25、50、75、100、125、...它们都满足相乘后产生至少两个0，在第一次5*k分析中已经统计过一次。对于N=101，是20。因此此处的5*5*k只要统计一次4即可，不需要根据25是5的二次幂统计两次。
后面的125,250,...等乘积为1000的可以为结果贡献3个0的数字，只要在5*5*k的基础上再统计一次n3=((N/5)/5)/5即可。
其实到这里已经不用再写，规律已经很清楚了。对于例子N=101，只要根据规律进行101/125=((101/5)/5)/5=4/5=0，退出统计。因此最终结果是20+4=24。计算结束。
下面编写打码实现上面的思想。
public class Solution {
public long trailingZeros(long n) {
long count = 0;
long temp=n/5;
while (temp!=0) {
代码分析：
算法中每次循环均有除以5的操作，也就是每次都会将所要处理的数据量缩小至上一次的1/5，容易推知时间复杂度为O(logN)。
至此，问题解决。
从最终的代码来看，问题是挺简单的。之所以折腾这么久都没有切入要害，直接做到真正的时间复杂度为O(logN)的效果，个人觉得是因为从分析题目的时候就没有真正理解O(logN)的真正含义。
类似于二叉搜索树，从根节点开始比较，比根节点小则与左子树比较，比根节点大则与右子树比较，相等或到达叶子节点则退出。如此循环迭代。
每次判断后，下一次可搜索的数据量均为上一次的1/2，如此循环复杂度为O(logN)。
遇到错误和不足就要反思，吸取教训。正视自己的缺点。
下面是个人吐槽时间，吃瓜子的观众可以有序退场了。
应该来讲，本题的最终目的是要做到O(logN)。分析题目的时候从O(logN)着手分析可能会是更好的方法。从科学的、有章可循的理论出发，作为指导思想，结合之前的例子（二叉搜索树），举一反三，解决本问题不是难事。
但是反过来，采用“朴素”方法，依靠个人经验，观察算法规律，然后解决问题。一个不行再去观察思考尝试下一种方法，虽然也是一种解决问题的思路，但如果想要在此基础上做到有章可循的逐步演进，怕是困难得多。
更何况如果观察不出规律呢？
先分析理论然后落实到实践，还是先动手做，再结合/总结升华出理论，值得推敲。
理性思考有助于身体健康，切记切记。与君共勉。
版权所有 爱编程 (C) Copyright 2012. . All Rights Reserved.
闽ICP备号-3
微信扫一扫关注爱编程，每天为您推送一篇经典技术文章。