千万不要被阶乘吓倒
更新时间：2020年4月25日 17:47 点击：1455
阶乘（Factorial）是个很有意思的函数，但是不少人都比较怕它，我们来看看两个与阶乘相关的问题：
1、 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N＝10，N！＝3 628 800，N！的末尾有两个0。
2、求N！的二进制表示中最低位1的位置。
有些人碰到这样的题目会想：是不是要完整计算出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的个数。
【问题1的解法一】
要计算Z，最直接的方法，就是计算i（i =1, 2, …, N）的因式分解中5的指数，然后求和：
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //统计N的阶乘中那些能够被5整除的因子的个数
j /= 5;
}
}
【问题1的解法二】
公式：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;
}
问题2要求的是N！的二进制表示中最低位1的位置。给定一个整数N，求N！二进制表示的最低位1在第几位？例如：给定N = 3，N！= 6，那么N！的二进制表示（1 010）的最低位1在第二位。
为了得到更好的解法，首先要对题目进行一下转化。
首先来看一下一个二进制数除以2的计算过程和结果是怎样的。
把一个二进制数除以2，实际过程如下：
判断最后一个二进制位是否为0，若为0，则将此二进制数右移一位，即为商值（为什么）；反之，若为1，则说明这个二进制数是奇数，无法被2整除（这又是为什么）。
所以，这个问题实际上等同于求N！含有质因数2的个数+1。即答案等于N！含有质因数2的个数加1。 实际上N！都为偶数，因为质因数里面都有一个2，除了1以外，因为1的阶乘是1，是个奇数，其他数的阶乘都是偶数。。
【问题2的解法一】
由于N! 中含有质因数2的个数，等于 N/2 + N/4 + N/8 + N/16 + …[1]，
根据上述分析，得到具体算法，如下所示：
/*
可以先求出N!中2的个数（因为每存在一个2，则在数的
最低位多1个0）。因此求1的最低位的位置即为N!中2的个数+1；
*/
int lowestOnePos(int n)
{
int ret = 0; //统计n!中含有质因数2的个数
while(n)
{
n >>= 1;
ret += n;
}
return ret+1;
}
【问题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
= 1111 + 111 + 1
=（10000 -1）+（1000 - 1）+（10-1）+（1-1）
= 11011-N二进制表示中1的个数
小结
任意一个长度为m的二进制数N可以表示为N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二进制数第i位上的数字（1或0）。所以，若最低位b[1]为1，则说明N为奇数；反之为偶数，将其除以2，即等于将整个二进制数向低位移一位。
相关题目
给定整数n，判断它是否为2的方幂（解答提示：n>0&&（（n&（n-1））==0））。
--------------------------------------------------------------------------------
[1] 这个规律请读者自己证明（提示N/k，等于1, 2, 3, …, N中能被k整除的数的个数）。
1、 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N＝10，N！＝3 628 800，N！的末尾有两个0。
2、求N！的二进制表示中最低位1的位置。
有些人碰到这样的题目会想：是不是要完整计算出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的个数。
【问题1的解法一】
要计算Z，最直接的方法，就是计算i（i =1, 2, …, N）的因式分解中5的指数，然后求和：
复制代码 代码如下:
ret = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j % 5 ==0)
{
ret++; //统计N的阶乘中那些能够被5整除的因子的个数
j /= 5;
}
}
【问题1的解法二】
公式：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;
}
问题2要求的是N！的二进制表示中最低位1的位置。给定一个整数N，求N！二进制表示的最低位1在第几位？例如：给定N = 3，N！= 6，那么N！的二进制表示（1 010）的最低位1在第二位。
为了得到更好的解法，首先要对题目进行一下转化。
首先来看一下一个二进制数除以2的计算过程和结果是怎样的。
把一个二进制数除以2，实际过程如下：
判断最后一个二进制位是否为0，若为0，则将此二进制数右移一位，即为商值（为什么）；反之，若为1，则说明这个二进制数是奇数，无法被2整除（这又是为什么）。
所以，这个问题实际上等同于求N！含有质因数2的个数+1。即答案等于N！含有质因数2的个数加1。 实际上N！都为偶数，因为质因数里面都有一个2，除了1以外，因为1的阶乘是1，是个奇数，其他数的阶乘都是偶数。。
【问题2的解法一】
由于N! 中含有质因数2的个数，等于 N/2 + N/4 + N/8 + N/16 + …[1]，
根据上述分析，得到具体算法，如下所示：
复制代码 代码如下:
/*
可以先求出N!中2的个数（因为每存在一个2，则在数的
最低位多1个0）。因此求1的最低位的位置即为N!中2的个数+1；
*/
int lowestOnePos(int n)
{
int ret = 0; //统计n!中含有质因数2的个数
while(n)
{
n >>= 1;
ret += n;
}
return ret+1;
}
【问题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
= 1111 + 111 + 1
=（10000 -1）+（1000 - 1）+（10-1）+（1-1）
= 11011-N二进制表示中1的个数
小结
任意一个长度为m的二进制数N可以表示为N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二进制数第i位上的数字（1或0）。所以，若最低位b[1]为1，则说明N为奇数；反之为偶数，将其除以2，即等于将整个二进制数向低位移一位。
相关题目
给定整数n，判断它是否为2的方幂（解答提示：n>0&&（（n&（n-1））==0））。
--------------------------------------------------------------------------------
[1] 这个规律请读者自己证明（提示N/k，等于1, 2, 3, …, N中能被k整除的数的个数）。
相关文章
- 这篇文章主要介绍了C语言实现的阶乘，排列和组合的方法,涉及C语言数学运算的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了python递归函数求n的阶乘,优缺点及递归次数设置方式，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-10
- 本篇文章是对c语言中实现N阶乘的程序代码进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- C#知识点记录编程的点点滴滴,本文整理了一些(传值调用与引用调用/打印三角形/递归求阶乘/多态性..等等)，感兴趣的朋友可以了解下的，不要走开(有图有真相)...2020-06-25
- 这篇文章主要介绍了Python 怎么定义计算N的阶乘的函数，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 今天小编就为大家分享一篇关于C语言测试n的阶乘和x的n次方，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言求N的阶乘的方法,包括一道相关的ACM题目示例,需要的朋友可以参考下...2020-04-25
- C# 实现阶乘 (递归,非递归) 实现代码，需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了c语言求阶乘精确值示例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了详解用python的阶乘，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-10-04
- 这篇文章主要介绍了C++求阶乘的两种方法，有需要的朋友可以参考一下...2020-04-25
- 这篇文章主要为大家详细介绍了Java实现递归计算n的阶乘，利用递归的思想实现阶乘的计算，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-08-27
- 这篇文章主要介绍了C#采用递归实现阶乘的方法,很有借鉴价值的一个算法技巧,需要的朋友可以参考下...2020-06-25
- 递归就是在过程或函数里调用自身,在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序...2021-09-22
- 本篇文章对c++的大数阶乘进行了代码示例的介绍。需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了Java编写程序之输入一个数字实现该数字阶乘的计算,本文通过实例代码给大家介绍的非常想详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-02-05
- 这篇文章主要给大家介绍了关于c语言阶乘之和问题的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用c语言具有一定的参考学习价值，需要的朋友们下面来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了Python3 实现递归求阶乘的操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-10
- 这篇文章主要介绍了Java两种方法计算出阶乘尾部连续0的个数，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-03-21
- 本篇文章是对阶乘进行了详细的分析介绍，需要的朋友参考下...2020-04-25