对任意输入的正整数N，编写C程序求N!的尾部连续0的个数。
上一篇 /
下一篇 2007-10-24 18:20:56
/ 个人分类：算法
//如：18！＝6402373705728000，尾部连续0的个数是3。51Testing软件测试网5}xW,?1q1h$S7K.v ].C
//问题直接的解法当然是直接求结果然后判断尾数0的个数。但是效率非常慢，是不是一定要有了结果才能知道
2V,f b H;pc
U0//结果有几个0呢,找一下规律就可以发现，尾数为0实际就是10的倍数，1个10可以分解为2*5就再不能分解了，51Testing软件测试网7nn b p nr
O |}
//所以要判断0的个数实际上是判断有几个2*5，问题就可以简单化了，针对这道题目，51Testing软件测试网:mG"kS*a_ Q
//实际只要知道N！中有几个数是2*5的对就解决了。
#include "stdafx.h"51Testing软件测试网? a2Bp8M \s'J
#define Max 50
int FiveCount(int i)51Testing软件测试网sR LFi2["L
{
7K9U7mJ4t8X0 int j,sum = 0;51Testing软件测试网L aO/dhI6cS
j = i/5;51Testing软件测试网oC:E2T:y
pa!A
sum = 1;51Testing软件测试网T:V q[nc @
while(j%5==0){51Testing软件测试网m!pd VM V `G
j=j/5;51Testing软件测试网&q*dw ~m7XA$R3q
sum++;
+]O&] @_*D0 }51Testing软件测试网A*I? Zxs7H o:T
return sum;51Testing软件测试网,Z1S!eP0a$? c
};
int TwoCount(int i)
8c'w q!S#k0{51Testing软件测试网x,c#o[h
int j,sum = 0;
st
ge3h0 j = i/2;51Testing软件测试网o.?2q
~ H#r iec
sum = 1;51Testing软件测试网3V8y` I&Q Ttyt2\
while(j%2==0){51Testing软件测试网 ~(h%A9b O+} J
U
j=j/2;
/yg&H9[~Ge9Ik0 sum++;
s Y'I8NB0 }51Testing软件测试网6g3say9nc#U;^+Q
return sum;51Testing软件测试网 NB%TCc5tR*d-J
}
int main(int argc, char* argv[])
4_#sy!N(ryN0{51Testing软件测试网 u+qGn7E#?2a(F F
int i;51Testing软件测试网9Kow+J/J b W D
int sum,CF,CT;
q]"l,J:O O[+?/meY0 sum = 1;
g7L)GO2Oe2H0 CF = 0;51Testing软件测试网gmG*SA$b;^
CT = 0;
1B l8e,ng0 for(i=1;i<=Max;i++)
w)z
})Z
T4bxo#L0 {
;cP2Q,@0DFa f,S0 if(i%5==0){51Testing软件测试网"q
L m0hb;C8SK0g;`
CF = CF + FiveCount(i); 51Testing软件测试网/j}5ln$|WTon
}
if(i%2==0){51Testing软件测试网,fT,k9@ a$Z*SK8|+u
CT = CT + TwoCount(i);
*})i cUB0 }
2D C-] Y)?2}0R0 }51Testing软件测试网f~7w#r;p R w)d ~MAx
if(CT>=CF){
y Z0RfF1LZ{0 printf("0-->%d",CF);
'n1G6N
k}0 }else{
Z"r'N`k!yb0 printf("0-->%d",CT);51Testing软件测试网;svT IwI G ?
}
:K FAY2W%cT0 return 0;
5b q_+Y0{4u.H8b*u5P0}
收藏
举报
TAG:
算法
