之前做的银联题目有一道题目就是1000的阶乘尾部有多少个0，记得这样的题目之前是做过的，但是当时就是时间太紧了没想起来，今天又遇到这个题目，索性查查看看是怎么算的，然后程序计算一下，加深理解，对于这样的题目网上也有很多的解法，核心的思想就是找规律看问题的本质是什么的，因为不可能让你求一下n!的阶乘然后自己去数一下一共末尾有多少个0，会溢出的。
思路：
如果想要尾部出现0必然离不开10的出现，而10的出现可以简化为2*5的结果，而在数字的分解中2的出现频数远高于5的出现频数，在这里的规律就是直接找n的因子分解中5的个数即可。
要找到n！的阶乘中尾部1的下标的思路同上，只需要寻找n中因数2的个数即可，因为这里返回的下标是从末尾开始数的所以在返回的结果中加1取反即可，因为Python中的末尾下标是从-1开始的。
有了这样的规律做起来就比较简单了，下面是具体的实现了：
#!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能：给定一个整数N,求N!末尾有多少个0,求N!的二进制中最低位1的位置 ''' def count_0_nums1(n): ''' 求N!末尾有多少个0 ''' num=n tmp=0 while num: tmp+=num/5 num/=5 print '{0}的阶乘末尾有{1}个0'.format(n, tmp) return tmp def count_0_nums2(n): ''' 求N!末尾有多少个0 ''' res=0 for i in range(5,n+1,5): index=i while index%5==0: res+=1 index/=5 print '{0}的阶乘末尾有{1}个0'.format(n, res) def find_tail_1_position(n): ''' 求N!的二进制中最低位1的位置 ''' temp=n res=0 while temp: temp>>=1 res+=temp print '{0}的二进制中最低位1的位置在{1}'.format(n, -(res+1)) if __name__ == '__main__': num_list=[4,10,6,12,100,1000] for one in num_list: count_0_nums1(one) print '----------------------------------------' for one in num_list: count_0_nums2(one) print '------------------------------------------' for one in num_list: find_tail_1_position(one)
结果如下：
4的阶乘末尾有0个0 10的阶乘末尾有2个0 6的阶乘末尾有1个0 12的阶乘末尾有2个0 100的阶乘末尾有24个0 1000的阶乘末尾有249个0 ---------------------------------------- 4的阶乘末尾有0个0 10的阶乘末尾有2个0 6的阶乘末尾有1个0 12的阶乘末尾有2个0 100的阶乘末尾有24个0 1000的阶乘末尾有249个0 ------------------------------------------ 4的二进制中最低位1的位置在-4 10的二进制中最低位1的位置在-9 6的二进制中最低位1的位置在-5 12的二进制中最低位1的位置在-11 100的二进制中最低位1的位置在-98 1000的二进制中最低位1的位置在-995 [Finished in 0.3s] 顺便说一下，考试遇到的那个题目问1000!末尾有 多少个0，它给的选项都是四位数的，我选的是2499，貌似所有选项尾部都是9，应该是题目出错了吧，其实当时就怀疑不可能会有几千个0的，差点想写个小程序算一下，毕竟服务器的话还是ok的。
