来源:编程之美 2.2
题目:1.给定一个整数N,求N!末尾有多少个0
2.求N!的二进制表示中最低位1的位置
对于第一个问题,书中也给出了两种解答方法,第二种是最好的,想明白为什么这样做后就很简单了。
/**
* 1.给定一个整数N,求N!末尾有多少个0 2.求N!的二进制表示中最低位1的位置
*/
public class Factorial2_2 {
public static void main(String[] args){
int num=100;
System.out.println(zeroCount1(num));
System.out.println(zeroCount2(num));
}
// 解法一,有多少个0,其实可以转化成求因式分解后5的指数是多少
public static int zeroCount1(int n) {
int res = 0;
int i, j;
for (i = 1; i <= n; i++) {
j = i;
while (j % 5 == 0) {
res++;
j /= 5;
}
}
return res;
}
//解法二,连续的k个数有且仅有1个数可以被k整除,如2,3,4,5,6肯定只有一个5可以被5带除
//如n=100时,可以把100,99,98....1五个五个分成一组,能分多少组就说明有多个数能被5整除
//接着计算有多少个数能被25,125...整除
//这就是书中给出的公式来源:Z = [N/5] +[N/5^2] +[N/5^3] + …
//(不用担心这会是一个无穷的运算,因为总存在一个K,使得5^K > N,[N/5^K]=0。)
public static int zeroCount2(int n) {
int res = 0;
while(n>0){
res+=n/5;
n/=5;
}
return res;
}
}
第二个问题的解法和第一个问题差不多,只不过是求2的质因数个数
//第二个问题实际上可以转化成求n!中含有质因数2的个数,最后加上1即可,解法和求5的是一致的
public static int lowestOne1(int n){
int res=0;
while(n>0){
n>>=1;
res+=n;
}
return res+1;
}
//N!含有质因数2的个数,还等于N减去N的二进制表示中1的数目
//这个思路比较难想~~
public static int lowestOne2(int n){
return n-count3(n)+1;
}
//整数二进制表示中1的个数,只需循环1的个数次即可
//每次循环都把最低位的1去掉了
public static int count3(int a){
int count=0;
while(a>0){
count++;
a&=(a-1);//通过&运算把最低位的1变成0
}
return count;
}
扩展问题:给定整数n,判断它是否为2的方幂
这个问题比较简单,只要是2的方幂的数,二进制表示都只有一个1,前面讲过n&(n-1)会把最低位的1变成0,因此只需要判断n&(n-1)是否为0即可:
//判断整数n是否为2的方幂
public static boolean isMiTwo(int n){
if(n>0&&((n&(n-1))==0))return true;
return false;
}
分享到:
相关推荐
向您详细介绍关于阶乘的各种编程快速方案与方法,您一定会有所收获的。
阶乘(Factorial)是个很有意思的函数,但是不少人都比较怕它,我们来看看两个与阶乘相关的问题: 1、 给定一个整数N,那么N的阶乘N!末尾有多少个0呢?例如:N=10,N!=3 628 800,N!的末尾有两个0。2、求N!的...
java阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘阶乘
阶乘 阶乘计算 大数阶乘 大整数阶乘 用数组计算阶乘
阶乘是基斯顿·卡曼(Christian Kramp,1760~1826)于 1808 年发明的运算符号,是数学术语。 一个正整数的阶乘(factorial)是所有小于及等于该数的正整数的积,并且0的阶乘为1。自然数n的阶乘写作n!。1808年,...
100阶乘100阶乘100阶乘100阶乘100阶乘100阶乘100阶乘100阶乘
VB 递归求阶乘 VB 递归求阶乘 VB 递归求阶乘
leetcode中国 Contents Chapter ...不要被阶乘吓倒 位运算的一些应用(如果将数看成是某种进制数位幂的连加) 2.3 寻找发帖的“水王” 妙用抵消法 有一个地方存疑:对于N-1个元素,需要多少次遍历才能
阶乘算法 阶乘问题 C# 小程序 这个是我用C#写的一个校程序,阶乘问题, 是以前学编程时写的,希望代码对大家有所帮助!
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘
整数的阶乘(英语:factorial)是所有小于及等于该数的正整数的积,0的阶乘为1。即:n!=1×2×3×…×n。 首先导入math模块,然后调用factorial()函数来计算阶乘。 1 math.factorial(x) import math value = math....
安徽大学计算机组成原理课程设计微程序实现阶乘
求该大数的阶乘的算法,初始化存储结果的数组,计算大数的阶乘的算 法。该程序的编程思想是因为大数求得阶乘后的数字太大,占据的空间 很大,所以必须利用数组来存储所得的结果,这样就必须确定所得的结 果所占的...
c语言1到20阶乘
1至n各自阶乘之和,适宜初学者代码使用,并非最优仅供参考,谢谢合作
易语言循环求阶乘源码,循环求阶乘,求阶乘
数据结构算法与应用代码,大数阶乘,通过单链表实现大数阶乘,对比较的书进行阶乘运算,主要是通过单链表实现
n! 大数的阶乘 c++ n! 大数的阶乘 cn! 大数的阶乘 c++++
易语言递归算法求阶乘源码,递归算法求阶乘,fac