题目:设计一个算法,计算出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) 作为判断条件求和即可
注意:不要暴力求解,阶乘的结果过大,很容易溢出