对于阶乘是个很有意思的函数,给定一个整数,那么它的阶乘是多少那?而它末尾有多少个0,
对于这个问题,是不是要直接计算N!?如果溢出怎么办,我们如何快速的找到该题的结果?首先要思考的N!= M*10^E。在N之前你需要看看那几个的成绩满足即可,比如2*5=10,所有2和5乘积就可以得到一个10,于是由于能被2整除的整数的频率要高于能被5整除的,所以我们可以取5考即可。
方法一从1开始到N,算出符合要求的个数。int result=0;
for(i = 1;i<=N;i++)
{
j = i;
while(j%5 == 0)
{
result++;
j/5;
}
}
或者是while(N)
{
result+=N/5;
N/=5;
}
类似可以求解二进制的问题,比如求N!的二进制中最低位1的位置。
由于N!中含有质数2的个数。等于N/2+N/4+N/8....1.
int lowOfone(int n)
{
int result = 0;
while (n)
{
n>>=1;
result+=n;
}
return result;
}
对于
给定整数n,判断它是否为2的方幂(解答提示:n>0&&((n&(n-1))==0))。
转载:
【N!二进制的解法二】
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,即等于将整个二进制数向低位移一位。
posted on 2011-09-29 13:51
mengkai 阅读(519)
评论(0) 编辑 收藏 引用 所属分类:
algorithm