黑马程序员技术交流社区

标题: 用Java基础前十课求1000！。 [打印本页]
作者: kaixinkai    时间: 2016-2-12 12:19
标题: 用Java基础前十课求1000！。
求1000！的结果中包含多少个0？注：1000! = 1×2×3×4×5×...×999×1000
只用java基础前十课的内容，不得用集合等超越前十课的知识。
作者: kaixinkai    时间: 2016-2-12 12:20
过20楼我会附上我自己的源码
作者: 洋葱头头    时间: 2016-2-12 12:29
过节呢 过20楼有点难
作者: kaixinkai    时间: 2016-2-12 12:59
洋葱头头 发表于 2016-2-12 12:29
过节呢 过20楼有点难

这是我们老师出的变态寒假作业16道其中的一道
作者: 宋达思    时间: 2016-2-12 13:04
本来我数学就不好，前些天才碰巧看了下阶乘，哎，数学全忘了
作者: kaixinkai    时间: 2016-2-12 13:25
宋达思 发表于 2016-2-12 13:04
本来我数学就不好，前些天才碰巧看了下阶乘，哎，数学全忘了

虽然我数学不错，高数也曾有满分，但是和编程并没有什么一丁点关系，人生最大的悲哀莫过于此，学过的东西不再用了。
作者: 酱油    时间: 2016-2-12 13:28
结果太大了，要用数组来存每一位的数字，
作者: 宋达思    时间: 2016-2-12 13:32
kaixinkai 发表于 2016-2-12 13:25
虽然我数学不错，高数也曾有满分，但是和编程并没有什么一丁点关系，人生最大的悲哀莫过于此， ...

也不能完全这么说，一个是数学学的好的人思维快，学编程理解起来肯定比一般人要快一些，另外，可能一般Java里是不怎么用数学知识的，但是可能会涉及到一些算法问题，像我们老师他学Hadoop的时候，里面就有，肯定还是有好处的。当然最悲剧的的确还是学完了却不用，肯定忘。
作者: ChiCaoMa    时间: 2016-2-12 14:06
我是来盖楼的--
作者: kaixinkai    时间: 2016-2-12 15:00
宋达思 发表于 2016-2-12 13:32
也不能完全这么说，一个是数学学的好的人思维快，学编程理解起来肯定比一般人要快一些，另外，可能一般Jav ...

你学的是什么班级？在哪儿的校区？我是安卓开发，现在在学Java基础，在北京校区。
作者: 宋达思    时间: 2016-2-12 18:26
kaixinkai 发表于 2016-2-12 15:00
你学的是什么班级？在哪儿的校区？我是安卓开发，现在在学Java基础，在北京校区。 ...

我是学JavaEE的，今年1月15号的基础班，在北京校区，渣渣1个，还请多指教哦
作者: kaixinkai    时间: 2016-2-13 08:54
宋达思 发表于 2016-2-12 18:26
我是学JavaEE的，今年1月15号的基础班，在北京校区，渣渣1个，还请多指教哦 ...

中关村二期软件园校区是吧，今年要搬校区了，你们javaee搬吗？
作者: kaixinkai    时间: 2016-2-13 08:58
酱油 发表于 2016-2-12 13:28
结果太大了，要用数组来存每一位的数字，

想不清楚在不能先算出结果的情况下如何边算边存，求版主指点
作者: 宋达思    时间: 2016-2-13 09:08
kaixinkai 发表于 2016-2-13 08:54
中关村二期软件园校区是吧，今年要搬校区了，你们javaee搬吗？

听老师说3月基础班结课以后才搬呢，前提是你要考上就业班，所以这个问题我暂时不想。
作者: 洋葱头头    时间: 2016-2-13 09:14
kaixinkai 发表于 2016-2-13 08:58
想不清楚在不能先算出结果的情况下如何边算边存，求版主指点

我不会啊
作者: 洋葱头头    时间: 2016-2-13 09:17
kaixinkai 发表于 2016-2-13 08:58
想不清楚在不能先算出结果的情况下如何边算边存，求版主指点

算出结果在计算0的个数把
作者: 宋达思    时间: 2016-2-13 09:47
本帖最后由 宋达思 于 2016-2-13 10:21 编辑

对于这个题，其实不难，但是只用前10天的知识，还不能先算出结果，反正我不会，太渣。咱们基础班讲的东西应该都一样吧，我想到的就是先算出阶乘的结果，这个简单，循环就行了。然后估计结果非常大吧，所以保险点用long来接收，然后就是10天以后的知识了，把long转成String字符串，会用Java API的话你不知道也能查到对应的方法，然后还是用String的方法，再将其转换成字符数组，之后就简单了，定义1个int类型的变量，初始值为0，也就是计数器，再遍历这个字符数组，每个角标的元素都字符'0'进行比较，如果返回true就让计数器自增，最后返回计数器的值即可。当然我用了10天以后的知识，不然我也不会。
作者: 张金金金    时间: 2016-2-13 12:05
mark一记，看完前十课我再来试试。
作者: bolt    时间: 2016-2-13 18:03
本帖最后由 bolt 于 2016-2-13 18:05 编辑
宋达思 发表于 2016-2-13 09:47
对于这个题，其实不难，但是只用前10天的知识，还不能先算出结果，反正我不会，太渣。咱们基础班讲的东西应 ...

需要对数的认识１０＝２＊５　１００＝４＊２５　　1000=8*125   10000=625*16
因为结果是含因数２比含因数５多
　个人认为就是算出这有多少个5的倍数　多少个２５的倍数　多少个１２５的倍数　　６２５的倍数
这样一想就有方法了。
具体用遍历来解决貌似就行。
作者: 宋达思    时间: 2016-2-13 18:14
好高端，数学渣渣，膜拜{:3_46:}
作者: 酱油    时间: 2016-2-13 19:26
kaixinkai 发表于 2016-2-13 08:58
想不清楚在不能先算出结果的情况下如何边算边存，求版主指点

用数组从0开始存储1000！的结果的每位数字，先从低位算，比如定义num[2000]，最初除了num[0]所有元素赋值0，然后从num[0]开始，每个数组元素都去乘1，乘2，乘3……并赋值给该数组元素，不过每次乘完后要判断是否大于10，因为我们用的是十进制，当没一位上的数大于10就会进1.。
比如。最开始，num[0]=num[0]*1 =1、num[0]=num[0]*2=2、num[0]=num[0]*3=6、、、、、、
                     当num[0]=num[0]*4=24时。因为num[0]相当于是个位。此时大于10，需要向num[1]（表示十位）进位，将num[0]除以10，取十位上的2,即num[1]从0变成了2,。对num[0]此处对10求余，所以num[0]则从24变成了4..............其他位也这么来做，。应该可以算出来吧，，我记得原来做过这种大数的算法题，书上就是这么讲的。
（讲的貌似不怎么清楚，见谅。以前做的题，刚刚去看了一下，那时候是用C做的，所以要用数组来存结果，，。其实对于java，这种大数的算法题，有一个变态的方法，就是使用BigInteger类，很快就出来了。。。。）

作者: DDK畅    时间: 2016-2-13 19:50
已过二十楼， 赶紧上代码吧  
作者: 513402004    时间: 2016-2-13 22:45
偶数乘以5就有零,两位数乘以五有一个或两个零.三位数有一个,两个,三个零.1000有三个零,分类一下呢,会不会好算点.
作者: 513402004    时间: 2016-2-13 23:17
挣扎了好久,觉得自己够猪脑袋得了..

QQ截图20160213231540.png (8.12 KB, 下载次数: 28)

QQ截图20160213231540.png
作者: kaixinkai    时间: 2016-2-14 16:28
513402004 发表于 2016-2-13 23:17
挣扎了好久,觉得自己够猪脑袋得了..

你说的这个应该是算最后有多少个零的算法
作者: kaixinkai    时间: 2016-2-14 18:10
酱油 发表于 2016-2-13 19:26
用数组从0开始存储1000！的结果的每位数字，先从低位算，比如定义num[2000]，最初除了num[0]所有元素赋值 ...

感谢大神，在你的思想指导下结合百度终于搞出来了
作者: kaixinkai    时间: 2016-2-14 18:13
诚挚感谢酱油的思路指导和宋思达的热情讨论，以及各位码友的顶贴。
首先道个歉，其实发帖的时候我也没理清楚整个流程及代码。
好在功夫不负有心人，在各位码友的指点下以及度娘的帮助，终于弄出来了，老师的作业实在是变态。
下边我会贴上我结合各方网友后整理出来的代码。
作者: kaixinkai    时间: 2016-2-14 18:17
Hello.zip (1.09 KB, 下载次数: 94)

class Hello {
        public static void main(String[] args) {
                //System.out.println("Hello World!");
                int[] res = new int[3000];
                final int limit = 1000;
                res[1] = 1;                              //从1索引开始是为了把索引值当做结果位数使用（后边遍历结果时不遍历零即可）   
                int max_now = 1;
                for (int step = 1;step <= limit;step++) {
                        int temp = 0;
                        int now = max_now;                   //定义每一次计算结果后的位数
                        int zero = 1;
                        for (zero =0;zero <= now;zero++) { //每次乘以阶数前先跳过数组末尾的0，提高计算效率
                                if (res[zero]!=0) {
                                        break;
                                }
                        }
                        for (int carry = zero-1;carry <= now ;carry++ ) {
                                res[carry] *= step;
                                res[carry] += temp;
                                temp = 0;
                                if (res[carry] >= 0) {
                                        int carry_temp = carry;
                                        temp = res[carry];                              //temp记录当前值并加上进位值
                                        if (carry_temp <= max_now) {                    //如果当前索引小于数值位数
                                                res[carry_temp] = temp%10;                  //索引指向值模以10并赋值当前索引指向值
                                                temp/=10;                                   //temp记录除以十后的值（即十进制进位值）
                                                carry_temp++;                               //索引向前移动一位
                                        }
                                        if (carry_temp > max_now) {                     //当前索引值（即结果第一位）大于数值位数
                                                while (temp >=10) {                         //判断结果第一位是否大于10
                                                        res[carry_temp] = temp%10;              //若大于，进位
                                                        temp /= 10;
                                                        carry_temp++;
                                                }
                                                res[carry_temp] = temp;
                                                temp = 0;
                                                max_now = carry_temp;                       //并将当前索引值赋值给位数
                                        }
                                }
                        }
                }
                //System.out.println(max_now);                         //去掉注释可打印一共有多少位
                int count = 0;
                for (int j = max_now;j >0 ;j-- ) {                     //取>0是为了去掉0索引指向的值，前边注释有指出
                        //System.out.print(res[j]);                        //去掉注释可遍历数组打印每一位
                        if (res[j] == 0) {
                                count ++;
                        }
                }
                //System.out.println();                                //去掉注释即可换行，区分计算结果与含零个数
                System.out.println(count);
                //下边这段代码用于计算末尾零的个数
                /*
                int count1 = 0;
                for (int k = 1;k < max_now;k++) {
                        if (res[k] != 0) {
                                break;
                        }
                        count1++;
                }
                System.out.println(count1);
                */
        }
}


作者: 安卓必备    时间: 2016-2-14 18:20
楼主现在上了多少天了?
作者: kaixinkai    时间: 2016-2-14 18:22
答案是含有零472个，末尾零的个数为249个
一下链接中有以前的吧友用BigInteger暴力求解或其他的方法做的，有心可以做参考
http://bbs.itheima.com/forum.php?mod=viewthread&tid=132784
本帖此题的关键思想在于用基础知识模拟十进制
作者: kaixinkai    时间: 2016-2-14 18:23
安卓必备 发表于 2016-2-14 18:20
楼主现在上了多少天了?

年前上了半个月，年后后天开学。学到了基础班day12
作者: kaixinkai    时间: 2016-2-15 11:12
宋达思 发表于 2016-2-13 18:14
好高端，数学渣渣，膜拜

源码已出
作者: P神    时间: 2016-2-15 12:51

好高端，数学渣渣，膜拜
作者: oassuperhan    时间: 2016-2-15 17:26
好久没回来了，今天才看到这个问题。感觉用大数类BigInteger暴力计算太浪费时间了，没有效率，明明是个数学题。

1000！=1*2*3*……*1000=1*(2^n1)*(3^n2)*（5^n3）……也就是小于1000的质因子的幂的乘积。要想得出结果有多少个0，其实可以转换成2的指数n1和5的指数n3的较小值，这样子问题就大大简化了，算出1到1000的每一个数值有多少个2和5然后两个数字较小的数字就是结果。那么怎么计算2和5的素因子个数呢？其实很简单：就拿2做例子，1000！中的2的方次数=[1000/2]+[1000/(2^2)]+[1000/(2^3)]+……+[1000/(2^n)]=500+250+125+62+31+15+7+3+1=994,[]为取整运算，5也是同样的方法得出结果249。所以1000！的0的个数是249。
        利用这个方法不需要大整数，只需要几个short整数和循环运算就可以高效计算，哪怕计算1亿的阶乘也拥有极高的运算效率。其实只是利用了数论的一点基础知识。
作者: oassuperhan    时间: 2016-2-15 17:31
另外说一下，由于计算的算法可以明显看出，10因数分解成的2和5，由于5大于2，所以5的因子个数一定小于2的，所以只需要求解5的个数即可。如果题目复杂变成A的阶乘里有多少a*b*c*d(a<b<c<d,且都是质数)那么只需要求出A！里有多少d就可以了，结果是[A/(d)]+[A/(d^2)]+[A/(d^3)]+[A/(d^4)]+……
作者: 15856681986    时间: 2016-2-16 22:22
好高端，数学渣渣，膜拜
作者: 姚成晖    时间: 2016-2-16 23:46
本帖最后由 姚成晖 于 2016-2-17 00:01 编辑

用数组做 只能蒙一个大概的  结果的位数   少了就不行。  果断 BigInteger
作者: 姚成晖    时间: 2016-2-16 23:52
本帖最后由 姚成晖 于 2016-2-17 00:06 编辑
  1. import java.math.BigInteger;

  3. public class Demo {
  4.                 /**
  5.                  *         需求：求出1000的阶层所有零和尾部零的个数
  6.                  * */
  7.         public static void main(String[] args) {
  8.                 Demo1();             //所有零的个数为472
  9.                 Demo2();             //尾部零的个数为249
  10.         }

  12.         private static void Demo2() {
  13.                 BigInteger bi1 = new BigInteger("1");
  14.                 for(int x=1;x<=1000;x++){
  15.                         BigInteger bi2 = new BigInteger(x+"");
  16.                         bi1=bi1.multiply(bi2);
  17.                         }
  18.                 String str = bi1.toString();
  19.                 int count=0;
  20.                 str = new StringBuilder(str).reverse().toString();
  21.                 for(int x=0;x<str.length()-1;x++){
  22.                         if('0'==str.charAt(x)){
  23.                                 count++;
  24.                         }else{
  25.                                 break;
  26.                         }
  27.                 }
  28.                 System.out.println(count);
  29.         }

  31.         private static void Demo1() {
  32.                 BigInteger bi1 = new BigInteger("1");
  33.                 for(int x=1;x<=1000;x++){
  34.                         BigInteger bi2 = new BigInteger(x+"");
  35.                         bi1=bi1.multiply(bi2);
  36.                 }
  37.                 String str = bi1.toString();
  38.                 int count =0;
  39.                 for(int x=0;x<str.length();x++){
  40.                         if('0'==str.charAt(x)){
  41.                                         count++;
  42.                                 }
  43.                         }
  44.                         System.out.println(count);
  45.                 }
  46. }
复制代码

作者: zapoo    时间: 2016-2-17 09:21
因为1000的阶乘太大了,int放不下,为了方便,你可以输入阶乘值在int范围内的任何数,一下是代码和运行结果
package com.java.xxx;

import java.util.Scanner;

/*
* 求1000！的结果中包含多少个0？注：1000! = 1×2×3×4×5×...×999×1000
*/
public class Test {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                System.out.println("请输入一个数");
                int inputNumber = sc.nextInt();
                int count = 0;
                int num1 = 1;
               
                for(int i = 1; i <= inputNumber; i++) {
                        num1 *= i;
                }
                System.out.println(inputNumber + "的阶乘结果为:" + num1);
               
                while(num1 > 0) {
                        int num = num1 % 10;
                        num1 /= 10;
                        if(num == 0) {
                                count++;
                        }
                }
                System.out.println(inputNumber + "的阶乘结果中0的个数为:" + count + "个");
        }
}
作者: ynztlxdeai    时间: 2016-2-17 12:11
路过看看
作者: kaixinkai    时间: 2016-2-17 20:58
zapoo 发表于 2016-2-17 09:21
因为1000的阶乘太大了,int放不下,为了方便,你可以输入阶乘值在int范围内的任何数,一下是代码和运行结果
pac ...

1000！比较大，基本数据类型存不下，如何解决，这才是本题的考点
作者: sl943508135    时间: 2016-2-17 21:24
我是来看看的
作者: shiyedong    时间: 2016-2-18 01:47
宋达思 发表于 2016-2-12 18:26
我是学JavaEE的，今年1月15号的基础班，在北京校区，渣渣1个，还请多指教哦 ...

你好，我是2月25日基础班的学员。我想问下去到以后有什么需要注意的嘛？学习内容是不是跟官网上发布的自学视频一样？有没有入学测试什么的？求前辈告知。
作者: kaixinkai    时间: 2016-2-19 10:46
自顶
作者: 就是我    时间: 2016-2-21 13:22
思考了半天,本打算通过从低位到高位挨个打印出来,但发现不是说没法打印,由于存储值溢出,连到底是多少你都不知道,,到底溢出了多少次也不知道,如果未溢出前存储值已经接近Long.MAX_VALUE,很可能乘以几百后直接溢出了几百次,都没法下手了
作者: kaixinkai    时间: 2016-2-21 20:53
就是我 发表于 2016-2-21 13:22
思考了半天,本打算通过从低位到高位挨个打印出来,但发现不是说没法打印,由于存储值溢出,连到底是多少你都不 ...

前边的楼层有详细的解释
作者: wangxiaguang102    时间: 2016-2-21 21:02
现在还看不懂什么意思
作者: docwei    时间: 2016-2-21 22:26
宋达思 发表于 2016-2-13 09:47
对于这个题，其实不难，但是只用前10天的知识，还不能先算出结果，反正我不会，太渣。咱们基础班讲的东西应 ...

这个妹子的思维不错呢
作者: 15856681986    时间: 2016-2-21 22:54
貌似求不到吧，反正我是不会
作者: 就是我    时间: 2016-2-21 23:30
kaixinkai 发表于 2016-2-14 18:23
年前上了半个月，年后后天开学。学到了基础班day12

那也没几天呢啊
作者: 赵雄    时间: 2016-2-25 20:35
用数组从0开始存储1000！的结果的每位数字，先从低位算，比如定义num[2000]，最初除了num[0]所有元素赋值0，然后从num[0]开始，每个数组元素都去乘1，乘2，乘3……并赋值给该数组元素，不过每次乘完后要判断是否大于10，因为我们用的是十进制，当没一位上的数大于10就会进1.。
比如。最开始，num[0]=num[0]*1 =1、num[0]=num[0]*2=2、num[0]=num[0]*3=6、、、、、、
                     当num[0]=num[0]*4=24时。因为num[0]相当于是个位。此时大于10，需要向num[1]（表示十位）进位，将num[0]除以10，取十位上的2,即num[1]从0变成了2,。对num[0]此处对10求余，所以num[0]则从24变成了4..............其他位也这么来做，。应该可以算出来吧，，我记得原来做过这种大数的算法题，书上就是这么讲的。
（讲的貌似不怎么清楚，见谅。以前做的题，刚刚去看了一下，那时候是用C做的，所以要用数组来存结果，，。其实对于java，这种大数的算法题，有一个变态的方法，就是使用BigInteger类，很快就出来了。。。。）
作者: DDK畅    时间: 2016-2-25 21:37
一般人是算不出来的，现在通过这道题就能看出来 数学好的人学java是多么的占优势



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