A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 路国强 中级黑马   /  2014-1-20 14:53  /  1737 人查看  /  7 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

求1000!的结果中包含多少个0
1000! = 1×2×3×4×5×...×999×1000。这个如何做。小弟想了好久了,也没有结果。希望大牛相助。

评分

参与人数 1技术分 +1 收起 理由
黄晓鑫 + 1

查看全部评分

7 个回复

倒序浏览
遍历每一个字符,判断是否为0,然后++
回复 使用道具 举报
原题不是阶乘末尾有多少个零么?
回复 使用道具 举报
额,算法题,其实最费脑子的,但是参考网上的讨论,不算自己做出来的,只供你参考,希望对你有所帮助

一般类似的题目都会蕴含某种规律或简便方法的,阶乘末尾一个零表示一个进位,则相当于乘以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;
        }
}

评分

参与人数 1技术分 +1 收起 理由
黄晓鑫 + 1

查看全部评分

回复 使用道具 举报 1 0
本帖最后由 落木萧萧 于 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 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 ;

        }
       
}

评分

参与人数 1技术分 +1 收起 理由
黄晓鑫 + 1

查看全部评分

回复 使用道具 举报
[问题描述]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");
}
}

评分

参与人数 1黑马币 +10 收起 理由
黄晓鑫 + 10

查看全部评分

回复 使用道具 举报
宋星 发表于 2014-1-20 18:14
哥们,你这个算法是对的,但你有一句是需要改正一下:1000/5+1000/25+1000/125+1000/625=200+40+8+1=249
...

确实,我的错

评分

参与人数 1黑马币 +3 收起 理由
黄晓鑫 + 3 很给力!

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马