2. 尾部的零

题目:设计一个算法,计算出n阶乘中尾部零的个数(JAVA)

审题:输入:目标数n

           输出:n!尾部0的数量

分析:

        一、试数

        0  !:结果为1,尾部没0

        5  !:尾部0一共有1个,相关数5(与0以外任意偶数)

        10!:尾部0一共有2个,相关数:5、10

        15!:尾部0一共有3个,相关数:5、10、15

        20!:尾部0一共有4个,相关数:5、10、15、20

        25!:尾部0一共有6个,相关数:5、10、15、20、25

        到此处即可发现:尾部0的出现只要考虑个位中5,0出现的情况

        初步推测:结果与n/5有关

        二、特殊情况

        25:25=5*5;尾部可以带来2个0(处理方法:2*2*5*5)

        50:50=25*2,尾部可以带来2个0

        100:100=25*4,尾部可以带来2个0

        125:125=25*5,尾部可以带来3个0(处理方法:2*2*2*5*5*5)

        625:625=25*25,尾部可以带来4个0(处理方法:2*2*2*2*5*5*5*5)

        进一步推测:若相关数可以表达为:2的x次方乘以5的x次方,则它可以带来x个0

        回归题目可知:2的x次方的数,远多于5的x次方的数,所以题目的结果由5决定,与2无关

        三、结论

        对于某个数n:当n可以表示为5的x次方*任意偶数,它可以带来x个0

        输出结果可以表达为:n/5+n/25+n/125+……+n/5的x次方

        所以可以直接用 while(n/5!=0) 作为判断条件求和即可

注意:不要暴力求解,阶乘的结果过大,很容易溢出

         

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 描述 设计一个算法,计算出n阶乘中尾部零的个数 样例 11! = 39916800,因此应该返回 2 挑战 O(l...
    6默默Welsh阅读 851评论 0 0
  • 设计一个算法,计算出n阶乘中尾部零的个数样例11! = 39916800,因此应该返回 2.这其实是一个数学题,思...
    和蔼的zhxing阅读 1,716评论 0 0
  • 描述 设计一个算法,计算出n阶乘中尾部零的个数您在真实的面试中是否遇到过这个题? 是样例 11! = 39916...
    Airycode阅读 1,085评论 0 0
  • 题目描述 设计一个算法,计算出n阶乘中尾部零的个数 思路 n阶乘能产生尾数0,换言之就是问n阶乘能乘出多少个101...
    Yui丶西米大人阅读 1,657评论 0 0
  • 今天原本打算早早关店回家休息,但六点之后的客人是一波接着一波。 会踏进书店的人,我不敢说一定是很会读书的人,但至少...
    happy_lailai阅读 4,700评论 8 12