以前见过这题几次,也不记得是哪里的面试题了。
1024可计为N
解题方法有两种:
一、使用大整数运算,也算是“暴力求解”了。但只看可能的求解长度就下一跳啊。此法不可取。
二、运用数学理论不难发现:
1、结果0的个数是和其小于N中各位为5的个数不无关系的。不是5的倍数无论和哪个相乘都不可能出现个位为0的结果。
N以内的偶数个数肯定是大于5倍数的个数的(5和偶数相乘才可能增加末位0的个数)。
所以有a = N / 5;
2、再看一下25这个是不是有点特殊呢?25 * 4 = 100,能产生两个0,这是为什么呢?因为25 = 5 * 5;因为能产生多余0的个数是和包含因子5的个数相关的。
25 * 4 = 100,有两个0,100无论在和任何非10倍数的数相乘都不可能产生多余两个0的数。同理(75 = 25 * 3 = 5 * 5 *3)* 4 = 300;(125 = 5 * 5 * 5 )* 8 = 1000;
即一个数包含多少个因子5其就可以同足够的偶数相乘产生相同个数的末位0。
总结如下:N的阶乘中末位0的个数为:N/5 + N/25 + N/125 ……
计算测试程序:
#include <stdio.h> int zero_count(int n); int main(int argc ,char *argv[]) { printf("zero_count is %d...\n", zero_count(1024)); return 0; } int zero_count(int n) { int count = 0; while(n > 0) { n = n/5; count += n; } return count; }