不要被阶乘吓倒.pdf

1、写书评，赢取编程之美-微软技术面试心得 不要被阶乘吓倒 阶乘（Factorial）是个很有意思的函数，但是不少人都比较怕它，我们来看看两个与阶 乘相关的问题： 1. 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N10，N！3 628 800， N！的末尾有两个0。 2. 求N！的二进制表示中最低位1的位置。 2.2 写书评，赢取编程之美-微软技术面试心得 分析与解法 有些人碰到这样的题目会想：是不是要完整计算出 N！的值？如果溢出怎么办？事实上， 如果我们从“哪些数相乘能得到 10”这个角度来考虑，问题就变得简单了。 首先考虑，如果 N！= K10 M ，且 K 不能被 10 整除

2、，那么 N！末尾有 M 个 0。再考虑 对 N！进行质因数分解，N！=（2 x ）（3 y ）（5 z ），由于 10 = 25，所以 M 只跟 X 和 Z 相关，每一对 2 和 5 相乘可以得到一个 10，于是 M = min（X, Z）。不难看出 X 大于等于 Z， 因为能被 2 整除的数出现的频率比能被 5 整除的数高得多，所以把公式简化为 M = Z。 根据上面的分析，只要计算出 Z 的值，就可以得到 N！末尾 0 的个数。 【问题 1 的解法一】 要计算 Z，最直接的方法，就是计算 i（i =1, 2, , N）的因式分解中 5 的指数，然后求 和： 代码清单 2-6 ret = 0

3、; for(i = 1; i N，N/5 K =0。） 公式中，N/5表示不大于 N 的数中 5 的倍数贡献一个 5，N/5 2 表示不大于 N 的数中 5 2 的倍数再贡献一个 5，代码如下： ret = 0; while(N) ret += N / 5; N /= 5; 问题 2 要求的是 N！的二进制表示中最低位 1 的位置。给定一个整数 N，求 N！二进制表 示的最低位 1 在第几位？例如：给定 N = 3，N！= 6，那么 N！的二进制表示（1 010）的最低 位 1 在第二位。 写书评，赢取编程之美-微软技术面试心得 为了得到更好的解法，首先要对题目进行一下转化。 首先来看一下一个

4、二进制数除以 2 的计算过程和结果是怎样的。 把一个二进制数除以 2，实际过程如下： 判断最后一个二进制位是否为 0，若为 0，则将此二进制数右移一位，即为商值（为什 么）；反之，若为 1，则说明这个二进制数是奇数，无法被 2 整除（这又是为什么）。 所以，这个问题实际上等同于求 N！含有质因数 2 的个数。即答案等于 N！含有质因数 2 的个数加 1。 【问题 2 的 解法一】 由于 N! 中含有质因数 2 的个数，等于 N/2 + N/4 + N/8 + N/16 + 1 ， 根据上述分析，得到具体算法，如下所示： 代码清单 2-7 int lowestOne(int N) int Ret

5、 = 0; while(N) N = 1; Ret += N; return Ret; 【问题 2 的 解法二】 N！ 含有质因数 2 的个数， 还等于 N 减去 N 的二进制表示中 1 的数目。 我们还可以通过 这个规律来求解。 下面对这个规律进行举例说明， 假设 N = 11011，那 么 N!中含有质因数 2 的个数为 N/2 + N/4 + N/8 + N/16 + 即： 1101 + 110 + 11 + 1 = （1000 + 100 + 1） + （100 + 10） + （10 + 1） + 1 = （1000 + 100+ 10 + 1）+（100 + 10 + 1）+ 1

6、= 1111 + 111 + 1 = （10000 -1）+（1000 - 1）+（10-1）+（1-1） 1 这个 规律请 读者 自己证 明（提示 N/k ，等 于 1, 2, 3, , N 中能被 k 整 除的 数的个数 ）。 写书评，赢取编程之美-微软技术面试心得 = 11011-N 二进制表示中 1 的个数 小结 任意一个长度为 m 的二进制数 N 可以表示为 N = b1 + b2 * 2 + b3 * 2 2+ + bm * 2 (m - 1) ，其中 b i 表示此二进制数第 i 位上的数字（1 或 0）。所以，若最低位 b1为 1，则说 明 N 为奇数；反之为偶数，将其除以 2，即等于将整个二进制数向低位移一位。 相关题目 给定整数 n，判断它是否为 2 的方幂（解答提示：n0&（n&（n-1）=0）。