不要被阶乘吓倒.pdf
《不要被阶乘吓倒.pdf》由会员分享,可在线阅读,更多相关《不要被阶乘吓倒.pdf(4页珍藏版)》请在文库网上搜索。
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 在第二位。 写书评,赢取编程之美-微软技术面试心得 为了得到更好的解法,首先要对题目进行一下转化。 首先来看一下一个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 不要 阶乘 吓倒