求100！中的0的个数？

Yuboo_J 2009-02-18 12:53:50

今天是实习的第二天，老师在讲到循环的时候问了我们一个问题.100！中含有几个0？
中午时间，我仔细想了一下，认为只要求出有多少个5的倍数就能知道答案，可却忽略了数与树之间的加法也能得出0.
我至今仍未想出合理的方法来解决这个问题？
请问有谁能给出一个合理的算法！
谢谢！

...全文

340 26 打赏收藏转发到动态举报

写回复

用AI写文章

26 条回复

切换为时间正序

请发表友善的回复…

发表回复

gbjgg 2009-04-10

打赏
举报

ding

lili830209 2009-04-10

打赏
举报

ding

Lonely_Tree 2009-04-10

打赏
举报

[Quote=引用 20 楼 Lonely_Tree 的回复:]
这个主要是计算100！包含5的因子的个数和2的个数。
,然而2的个数显然要大于5的个数，所以只关注5的个
数然后100！中有多少个5的因子，那么就需要数论的
知识了。好像是[100/5]+[100/5^2];
即为答案，具体可以查看数论资料！
[/Quote]

public class MyClass{
public static void main(String[]args){
int data = 100; //求data阶乘末尾包含多少个0.
int i = 5 ;
int count = 0;
while(data/i!=0) {
count+=(data/i);
i*=i;
}
System.out.println(data+"阶乘末尾0个数是:"+ count);
}
}

jichangh1983 2009-04-08

打赏
举报

学习了

kanwangzjm 2009-04-08

打赏
举报

非常高效的代码可以计算到1000！

int data[20000];
int num;//阶乘大小
int digit;//每次阶乘得出结果的位数
while(1){
scanf("%d",&num);if(num<0) break;digit=1;memset(data,0,sizeof(data));
data[0]=1;data[1]=1;
for(int i=1;i<=num;i++)
{
for(int j=1;j<=digit;j++)//先做每一位与i的乘积放在一个数组空间中
{data[j]*=i;}
for( j=1;j<=digit;j++)//调整个元素的值,使之在0--9之间
{if(data[j]>9)
{for(int k=1;k<=digit;k++){
if(data[digit]>9) //位数增加
{digit++;}
data[k+1]+=data[k]/10;//调整
data[k]%=10;}}}}
for(int j=digit;j>0;j--)
{printf("%d",data[j]);}

zmjsg 2009-04-05

打赏
举报

顶。。。

Lonely_Tree 2009-04-04

打赏
举报

这个主要是计算100！包含5的因子的个数和2的个数。
,然而2的个数显然要大于5的个数，所以只关注5的个
数然后100！中有多少个5的因子，那么就需要数论的
知识了。好像是[100/5]+[100/5^2];
即为答案，具体可以查看数论资料！

yesvery 2009-03-02

打赏
举报

不会使用BigInteger类型，否则程序会更简单。
还望高手指教

yesvery 2009-03-02

打赏
举报

不好意思，进位处理中有bug，应该把两条语句的前后位置对调以下
for(int i=0;i <149;i++){ //进位处理
b[i+1]=b[i+1]+b[i]/10;
b[i]=b[i]%10;
}
另外，各数组扩展为160个元素因为最终结果是158位

0093326215443944152681699238856266700490
7159682643816214685929638952175999932299
1560894146397615651828625369792082722375
8251185210916864000000000000000000000000

前2个零不算，中间6个零，末尾24个零，共30个零

Sodino 2009-03-02

打赏
举报

老紫竹博客有解

http://blog.csdn.net/java2000_net/archive/2009/02/19/3910401.aspx

yesvery 2009-03-01

打赏
举报

10楼说的有道理，根据5的个数只能求出尾部0的个数，中间的0没做考虑。
看来，只有参照亚日说的，利用字符串直接计算。
不过，需要自己编制字符乘法的九九表，编制带进位的字符加法。

heibing578604041 2009-03-01

打赏
举报

位运算就好了

superAfx 2009-03-01

打赏
举报

有这么复杂么？100！是100的阶乘，貌似没有加法的

counter = 0;
for (i = 1 i <=100; i++)
{
n = i;// 当前数字有几个5的因子，有一个多一个零
while (n % 5 == 0)
{
counter ++;
n /= 5;
}
}
循环结束后，自己打印counter :)

yesvery 2009-03-01

打赏
举报

public class aa {
static int[] a=new int[150];
static int[] b=new int[150];
static int[] c=new int[150];

public static void main(String[] arg){
int f=100;
for(int i=0;i<150;i++){
a[i]=0;
b[i]=0;
}
factorial(f);
for(int i=149;i>-1;i--) System.out.print(a[i]); 由高至低把各位打印出来
}

public static void factorial(int d){ //阶乘的方法
int e;
a[0]=1;
for(int k=1;k<=d;k++){
for(int i=0;i<150;i++){ //a数组的各元素与k相乘，结果放入数组b的相应元素中
e=a[i]*k;
if(e>=100){
b[i+2]=b[i+2]+e/100;
e=e%100;
}
if(e>=10){
b[i+1]=b[i+1]+e/10;
e=e%10;
}
b[i]=b[i]+e;
}
for(int i=0;i<149;i++){ //进位处理
b[i]=b[i]%10;
b[i+1]=b[i+1]+b[i]/10;
}
c=a; //利用c 进行a,b的交换
a=b;
b=c;
for(int i=0;i<150;i++) b[i]=0; //b数组清零
}
}
}
利用150个元素的数组，求出的答案如下：
000478250885038094923057851198
075878590702874186511249894093
290412323234811438398100663612
104680322341562443547956896035
479888000000000000000000000000

10！共147位，前3个零不算，中间14个零，末尾24个零，共38个零