黑马程序员技术交流社区

标题: 一道小问题，各路好汉，大神请进。 [打印本页]
作者: 路国强    时间: 2014-1-20 14:53
标题: 一道小问题，各路好汉，大神请进。
求1000！的结果中包含多少个0
1000! = 1×2×3×4×5×...×999×1000。这个如何做。小弟想了好久了，也没有结果。希望大牛相助。

作者: 浮出一个美    时间: 2014-1-20 15:20
遍历每一个字符，判断是否为0，然后++
作者: 落木萧萧    时间: 2014-1-20 15:40
原题不是阶乘末尾有多少个零么？
作者: 廉伟杰    时间: 2014-1-20 15:47
额，算法题，其实最费脑子的，但是参考网上的讨论，不算自己做出来的，只供你参考，希望对你有所帮助

一般类似的题目都会蕴含某种规律或简便方法的，阶乘末尾一个零表示一个进位，则相当于乘以10，而10 是由2*5所得，在1~100当中，可以产生10的有：2 4 5 6 8 结尾的数字，显然2是足够的，因为4、6、8当中都含有因子2，所以都可看当是2，那么关键在于5的数量了。
那么该问题的实质是要求出1~100含有多少个5

由特殊推广到一般的论证过程可得：

1、 每隔5个，会产生一个0，比如 5， 10 ，15，20……
2 、每隔 5×5 个会多产生出一个0，比如 25，50，75，100 ……
3 、每隔 5×5×5 会多出一个0，比如125.



所以100！末尾有多少个零为：

100/5+100/25=20+4=24

那么1000！末尾有多少个零呢？同理得：

1000/5+1000/25+1000/125=200+40+8=248


/*
        功能：判断1000！中有多少个零
*/
class  Demo
{
        public static void main(String[] args)
        {
                System.out.println("1000!中有"+(sum(1000))+"个零");
        }
        static int sum(int n)
        {
                int count = 0;
                while(n / 5 !=0)
                {
                        count +=n / 5;
                        n = n / 5;
                }
                return count;
        }
}
作者: 落木萧萧    时间: 2014-1-20 15:57
本帖最后由 落木萧萧 于 2014-1-20 16:16 编辑
落木萧萧 发表于 2014-1-20 15:40
原题不是阶乘末尾有多少个零么？

小学信息奥赛题……
借别人的思路：
思路一，一个约数5和一个约数2组成一个0。
然后约数5一定比约数2少……所以只要一个个扫过去然后每个都除以5看看能整除几次累加起来。
思路二，
[1000/5]=200
[1000/25]=40
[1000/125]=8
[1000/625]=1
加起来就是249

学java这么久，别的没学会，养成了遇到问题就百度的坏毛病。

作者: 宋星    时间: 2014-1-20 18:14
廉伟杰 发表于 2014-1-20 15:47
额，算法题，其实最费脑子的，但是参考网上的讨论，不算自己做出来的，只供你参考，希望对你有所帮助

一般 ...

哥们，你这个算法是对的，但你有一句是需要改正一下：1000/5+1000/25+1000/125+1000/625=200+40+8+1=249
是249个，不是248个。
其实光看代码的话有点难懂。
下面说一个好懂一点的方法。
10是由2*5所得，所以要找出从1~1000的每个数中的2和5的个数，例：75=5*5*3,75中有两个5，
          然后把所有的5和2的个数分别相加，哪个个数少，就是10的个数，也就是1000！末尾的0的个数
          虽然知道2的个数肯定比5的多，5的个数即是10的个数，作为验证，还是求出所有2的个数
public class Test7 {
        public static void main(String[] args)
        {
                System.out.println(endZeroCount(1000));
        }
        public static int endZeroCount(int number)
        {
                int count_2=0;                //定义2的总个数
                int count_5=0;                //定义5的总个数
                for(int i=1;i<=number;i++)
                {
                        int currentNumber=i;
                        //求出该数中的2的个数，必须要能被2整除
                        while (currentNumber%2==0)               
                        {
                                count_2++;                        //累加2的个数
                                currentNumber/=2;        //以循环的形式，不断的除以2，以便得出该数中2的个数
                        }

                        while (currentNumber%5==0)                //求5的个数，同上面求2的个数
                        {
                                count_5++;
                                currentNumber/=5;
                        }
                }       
                System.out.println(count_2);
                System.out.println(count_5);
                return count_5 ;

        }
       
}
作者: 姬运涛    时间: 2014-1-20 20:09
[问题描述]1*2*3*...*1000末尾有多说个连续的0?
1*2*3*...*1000是一个很大的数，这个数的末尾有多说个连续的0?

/*****************************************/
/**
* 算法描述(此程序未用BigInteger实现)：
* 分解质因数，即：
* 1*2*3*...*1000 = (2*5)*(2*5)*...*(2*5)
            *(没有匹配的2或5) //其实地球人都知道2肯定比5多
                                //这样其实只需要确定因子5的个数即可
            *(除2和5以外的其他质因数)
* 其因子中有多少个(2*5)即末尾有多少个0
* 因此问题变成求每个数中2和5因子的个数，再求和
* 最后min(因子2个数的总和，因子5个数的总和)即是所求。
*/
public class SumZero {
SumZero(){
  max = 1000;//默认值是1000
}
SumZero(int n){
  max = n;//可以通过构造函数修改max的值
}

private int max;
/**
  * 得到max的因子 m 的个数
  */
public int getFactor(int m){
  int count = 0，
      n = max;
  
  //try 中的便是程序的核心
  try{
  while(n%m == 0){//能被m整除则count++
  count++;
  if(n >= m){
    n /= m;
  }
  }
  }
  catch(Exception e){
  e.printStackTrace();
  }
  
  return count;   
}

/**
  * 得到末尾0的个数
  */
public int getNumber(){
  int count_2 = 0,//因子2的个数
    count_5 = 0;//因子5的个数

  for(int i = 1;i<=max;i++){
  count_2 += getFactor(i,2);//其实没有必要求因子2的个数
  count_5 += getFactor(i,5);
  }
  
  return Math.min(count_2,count_5);//必定有：count_5 < count_2
}
public static void main(String[] args){
  System.out.println("1*2*...*1000的末尾有"
                        +new SumZero().getNumber()
                        +"个0");
}
}
作者: 廉伟杰    时间: 2014-1-20 20:31
宋星 发表于 2014-1-20 18:14
哥们，你这个算法是对的，但你有一句是需要改正一下：1000/5+1000/25+1000/125+1000/625=200+40+8+1=249
...

确实，我的错



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2