微软编程之美官网_编程之美 pdf 百度云_编程之美

（1）给定一个整数N，那么N的阶乘N！末尾有多少个0？比如：N=10，N！=3628800,N！的末尾有2个0。编程之美

（2）求N！的二进制表示中最低位为1的位置。编程之美

这是编程之美一道经典的题目，一拿到题目很就懵了，不知从何下手，但是当我们换一种思路。

（1）考虑哪些组合可以得到10即可，考虑哪些数相乘能得到10，N!= K *10M其中K不能被10整除，则N!末尾有M个0.

对N!进行质因数分解：N!=2X*3Y*5Z…，因为10=2*5，所以M与2和5的个数即X、Z有关。每一对2和5都可以得到10，故M=min(X,Z)。因为能被2整除的数出现的频率要比能被5整除的数出现的频率高，所以M=Z。

因此你就会很快的写下下面的程序：

int countZero(int N) { int ret = 0; int j; for(int i=1; i<=N;i++) { j = i; while(0==j%5) { ret++; j /= 5; } } return ret;}

当然还有一种解法：

Z =[N/5] + [N/52] + [N/53] + …

[N/5] 表示不大于N的的数中5的倍数贡献一个5, [N/52] 表示不大于N的数中52的倍数在贡献一个5……

int countZero(int N) { int ret = 0; while(N) { ret += N/5; N /= 5;} return ret; }

（2）把一个二进制除以2的过程如下：

判断最后一个二进制是否为0：若为0将二进制数右移1位，即为商；若为1，则说明这个数是奇数，不能被2整除。所以判断N!的二进制表示中最低位为1的位置的问题可以转换为求N!中含有质因数2的个数的问题。即位置为N!含有质因数2的个数加1.

N!中含有质因数2的个数等于：[N/2]+[N/4]+[N/8]+…

int lo

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-27111-1.html