首页 / MYSQL / 【编程之美】2.2不要被阶乘吓到
【编程之美】2.2不要被阶乘吓到
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【编程之美】2.2不要被阶乘吓到，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2554字，纯文字阅读大概需要4分钟。
内容图文
题目： 1：给定一个整数N，那么N的阶乘N！末尾有多少个0？例如N = 10，N！= 3628800，末尾有两个0. 2：求N！的二进制表示中最低位1的位置。 问题一： 题目解析： 这道题如果直接求N！的话也可以，不过万一溢出了怎么办？即使定义longlong类型的也不合适。那
题目：
1：给定一个整数N，那么N的阶乘N！末尾有多少个0？例如N = 10，N！= 3628800，末尾有两个0.
2：求N！的二进制表示中最低位1的位置。
问题一：
题目解析：
这道题如果直接求N！的话也可以，不过万一溢出了怎么办？即使定义longlong类型的也不合适。那么就要找寻其中的规律，一般这类题目都可以通过分析，找到一个很简单的方法。
思路一：
我们想想0是怎么来的？乘以10就增加一个0，而10可以通过2*5的来。好了，我们将N!表达式表达出来，看能获得多少个2*5。N! = 2^x * 3^y * 5^z... 由于2比5小，所以x比z要大。所以看N!中有多少个5就可以了。
int Count(int n)
{
int num = 0;
for(int i = 1;i < n;++i){
int j = i;
while(j%5 == 0){
num++;
j /= 5;
}
}
}思路二：
我们可以利用公式Z = [N/5] + [N/(5^2)] + [N/(5^3)] +....
这个公式表达什么意思呢？N/5表示从1-N中有多少个数是5的倍数，那么这些数，每一个都贡献一个5；好了但是对于25会贡献两个，在除以5的时候，已经算进去1个，那么N/(5^2)的时候，看看有多少是25的倍数，也算一下，这时将25中的另一个5给算进去了；同理对于75，当我们N/75的时候，正好把三个5全算进去……通过这个方法，更简化程序的实现。
int Count1(int n)
{
int num = 0;
while(n){
num += n/5; //这种方法更简洁，避免了附设变量
n = n/5;
}
return num;
}问题二：
说白了，问题2跟问题1是一样的，求N!2的倍数。
思路一：
根据上题的情况，写出如下表达式求表达式N! = 2^x * 3^y * 5^z... 我们要求x的值为多少。也可以通过遍历1-N一个一个求解
int Count2(int n)
{
int num = 0;
for(int i =0;i < n;++i){
int j = i;
while(j%2 == 0){
num++;
j = j/2;
}
}
return num;
}
//当然可以通过位来操作
int Count_2(int n)
{
int num = 0;
for(int i =0;i < n;++i){
int j = i;
while(!(j & 1)){
num++;
j = j >> 1;
}
}
return num;
}思路二：
类似问题一中的公式，我们也可以写出Z = [N/2] + [N/(2^2)] + [N/(2^3)] +....
int Count3(int n)
{
int num = 0;
while(n){
n = n >> 1;
num += n; //这句话写在下面，更好
}
return num;
}思路三：
N!含有质因数2的个数，还等于N减去N的二进制表示中1的数目。——这是一种巧妙的方法，是根据Z = [N/2] + [N/(2^2)] + [N/(2^3)] +....运算得到的，因为除以2，相当于右移一位，对于11011我们有：
Z = 1101 + 110 + 11 + 1 = (1000 + 100 + 1) + (100 + 10) + (10 +1) + 1
= 1111 + 111 + 1 = (10000 - 1) + (1000 - 1) + (10 - 1) + (1 - 1) = 11011 - (N二进制中1的个数)
相关题目：
给定整数n，判断它是否为2的方幂。
（2的方幂为2^X。所以表示为二进制的时候，只有一位为1，那么利用判断二进制的个数的方法来判断： n>0 && ((n && (n-1)) == 0)）
内容总结
以上是互联网集市为您收集整理的【编程之美】2.2不要被阶乘吓到全部内容，希望文章能够帮你解决【编程之美】2.2不要被阶乘吓到所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。