對于階乘是個很有意思的函數(shù)，給定一個整數(shù)，那么它的階乘是多少那？而它末尾有多少個0，
對于這個問題，是不是要直接計算N!？如果溢出怎么辦，我們?nèi)绾慰焖俚恼业皆擃}的結(jié)果？首先要思考的N!= M*10^E。在N之前你需要看看那幾個的成績滿足即可，比如2*5=10，所有2和5乘積就可以得到一個10，于是由于能被2整除的整數(shù)的頻率要高于能被5整除的，所以我們可以取5考即可。
方法一從1開始到N，算出符合要求的個數(shù)。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;
}
類似可以求解二進(jìn)制的問題，比如求N!的二進(jìn)制中最低位1的位置。
由于N!中含有質(zhì)數(shù)2的個數(shù)。等于N/2+N/4+N/8....1.
int lowOfone(int n)
{
int result = 0;
while (n)
{
n>>=1;
result+=n;
}
return result;
}
對于
給定整數(shù)n，判斷它是否為2的方冪（解答提示：n>0&&（（n&（n-1））==0））。
轉(zhuǎn)載：
【N!二進(jìn)制的解法二】
N！含有質(zhì)因數(shù)2的個數(shù)，還等于N減去N的二進(jìn)制表示中1的數(shù)目。我們還可以通過這個規(guī)律來求解。
下面對這個規(guī)律進(jìn)行舉例說明，假設(shè) N = 11011，那么N!中含有質(zhì)因數(shù)2的個數(shù)為 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二進(jìn)制表示中1的個數(shù)
小結(jié)
任意一個長度為m的二進(jìn)制數(shù)N可以表示為N = b[1] + b[2] * 2 + b[3] * 22 + … + b[m] * 2(m-1)，其中b [ i ]表示此二進(jìn)制數(shù)第i位上的數(shù)字（1或0）。所以，若最低位b[1]為1，則說明N為奇數(shù)；反之為偶數(shù)，將其除以2，即等于將整個二進(jìn)制數(shù)向低位移一位。
posted on 2011-09-29 13:51
mengkai 閱讀(560)
評論(0) 編輯 收藏 引用 所屬分類:
algorithm