分类:
2010-06-18 23:29:21
不要被阶乘吓倒
阶乘(Factorial)是个很有意思的函数,但是不少人都比较怕它,我们来看看两个与阶乘相关的问题:
问题一:
给定一个整数N,那么N的阶乘N!末尾有多少个0呢?例如:N=10,N!=3 628 800,N!的末尾有两个0。
分析与解法
有些人碰到这样的题目会想:是不是要完整计算出N!的值?如果溢出怎么办?事实上,如果我们从"哪些数相乘能得到10"这个角度来考虑,问题就变得简单了。
首先考虑,如果N!= K×10^M,且K不能被10整除,那么N!末尾有M个0。再考虑对N!进行质因数分解,N!=(2^x)×(3^y)×(5^z)…,由于10 = 2×5,所以M只跟X和Z相关,每一对2和5相乘可以得到一个10,于是M = min(X, Z)。不难看出X大于等于Z,因为能被2整除的数出现的频率比能被5整除的数高得多,所以把公式简化为M = Z。
根据上面的分析,只要计算出Z的值,就可以得到N!末尾0的个数。
【解法一】
要计算Z,最直接的方法,就是计算i(i =1, 2, …, N)的因式分解中5的指数,然后求和:
代码清单2-6
- ret = 0;
- for(i = 1; i <= N; i++)
- {
- j = i;
- while(j % 5 ==0)
- {
- ret++;
- j /= 5;
- }
- }
这里我们可以减少循环的次数,由于只有5的倍数才能贡献5,所以,第一步,我们只需要将N除以5,就可以知道,有多少个数可以贡献5,然后再遍历小于N的所有的数,即可,可以得到程序代码:
这样,循环次数就减小为原来的1/5,同理,我们可以对[N/5],再除以5,就可以知道[N/5]能贡献几个5,以此类推,就得到书中的解法二。
【解法二】
公式:Z = [N/5] +[N/5^2] +[N/5^3] + …(不用担心这会是一个无穷的运算,因为总存在一个K,使得5^K > 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;
- }
求N!的二进制表示中最低位1的位置。
分析与解法:
乍一看,似乎,问题二与问题一没什么关系。然而,我们换一个角度思考,二进制中最低位1后面肯定是0,那
么这里求最低位1的位置,即为求最低位1后面0的个数,而这,就和问题一是一样一样的,只不过一个是十进制表
,一个是二进制表示。
这里,所有小于N的数中,2的倍数都贡献一个0,4的倍数再贡献一个0,以此类推,很容易写出如下代码:
相关题目
给定整数n,判断它是否为2的方幂.