黑马程序员技术交流社区

标题: 微软曾经的一道面试题！ [打印本页]
作者: 七弦    时间: 2014-5-26 20:48
标题: 微软曾经的一道面试题！
在网上看到一道题，听说是曾经微软出的题，暂时没看出来头绪。。


写一个程序实现：输入一个数，求它的阶乘后面有多少个连续的0，将其连续0 的个数输出。

可能有同学不知道阶乘，简单说一下：例如所要求的数是n，则阶乘式是1×2×3×……×n，设得到的积是x，x就是n的阶乘。
能写出来的上来秀秀！

作者: 韩长征    时间: 2014-5-26 23:31
  1. import java.util.regex.Matcher;
  2. import java.util.regex.Pattern;
  3. /**
  4. * 输入一个数，求它的阶乘后面有多少个连续的0，将其连续0 的个数输出。
  5.        例如所要求的数是n，则阶乘式是1×2×3×……×n，设得到的积是x，x就是n的阶乘。
  6.        分析：阶乘容易求出，将阶乘转成字符串，判断尾部是否有0.
  7.        设置一个正则表达式，将其取出即可
  8. * @author Administrator
  9. *
  10. */
  11. public class JieCheng {

  13.         public static void main(String[] args) {
  14.                 // TODO Auto-generated method stub
  15.                 getEndZero(20);
  16.         }
  17.         public static void getEndZero(int x ){
  18.                 int b = 1;
  19.                 //long b = 1; 没测试过
  20.                 for(int a=1;a<=x;a++){
  21.                         b = b*a;
  22.                 }
  23.                 //b这里定义的int类型，貌似给的数过大的话
  24.                 //其阶乘就超出int的取值范围，b就为负数了，考虑用long类型
  25.                 //x的值超过16就为负数了
  26.                 System.out.println("阶乘："+b);
  27.                 String str = b+"";
  28.                 //System.out.println(str);
  29.                 String reg = "0+$";
  30.                 if(str.endsWith("0")){
  31.                         Pattern p = Pattern.compile(reg);
  32.                         Matcher m = p.matcher(str);
  33.                         while(m.find()){
  34.                                 System.out.println(m.group());
  35.                                 System.out.println("后面0的个数："+(m.end()-m.start()));
  36.                         }
  37.                 }else{
  38.                         System.out.println(-1);
  39.                 }
  40.         }
  41. }
复制代码


看看这个代码可行不？
作者: 张百振    时间: 2014-5-26 23:43
个人建议楼上用BigInteger
作者: 西门吹风    时间: 2014-5-27 00:29
本帖最后由 西门吹风 于 2014-5-27 09:11 编辑

今天刚好看完for循环视频，尝试用for循环写了一下，这个数好像不能太大，不然超过long的范围，望高人指正
  1. /*
  2. 1、任意数先分为0和非0
  3. 2、非0时用for循环求阶乘积，分为正数、负数
  4. 3、用阶乘积与10取模看其余数是否为0，如果是则计数器加1，
  5. 然后用阶乘积除以10，相当于最后一个0去掉，再与10取模，
  6. 如此循环，直到去掉N个0后的阶乘积与10取模的余数不为0时
  7. 跳出循环。
  8. */
  9. class CountZero
  10. {
  11.         public static void main(String[] args)
  12.         {
  13.                 int x=15;      
  14.                 long sum=1l;      
  15.                 int count=0;           
  16.                 if(x!=0)                     
  17.                 {
  18.                         if(x>0)                     
  19.                         {
  20.                                 for(int i=1;i<=x;i++)        
  21.                                 {
  22.                                         sum=sum*i;
  23.                                 }
  24.                         }
  25.                         else if(x<0)            
  26.                         {
  27.                                 for(int i=-1;i>=x;i--)   
  28.                                 {
  29.                                         sum=sum*i;
  30.                                 }
  31.                         }
  32.                         for(long i=sum ;i%10==0 ;i=i/10)      
  33.                         {                                                      
  34.                                 count++;                                    
  35.                         }        
  36.                 }
  37.                 else                                                
  38.                 {
  39.                         count=1;
  40.                         sum=0;
  41.                 }
  42.                 System.out.println(sum);      
  43.                 System.out.println(count);
  44.         }
  45. }
复制代码



作者: zhrnghgwsws    时间: 2014-5-27 00:30
学习一下。
作者: 彭旭文    时间: 2014-5-27 01:27
学习一下...谢谢分享...
作者: 韩长征    时间: 2014-5-27 07:33
张百振 发表于 2014-5-26 23:43
个人建议楼上用BigInteger

刚刚看了下BigInteger，好像确实更好一些，谢谢。
3楼的想法很好。
作者: 七弦    时间: 2014-5-27 08:06
本帖最后由 七弦 于 2014-6-12 19:15 编辑

四楼输入的数超过20貌似就挂了，最多就能求出来4个0
作者: 七弦    时间: 2014-5-27 08:09
本帖最后由 七弦 于 2014-6-12 19:13 编辑

都很厉害！！！
作者: 七弦    时间: 2014-5-27 08:26
本帖最后由 七弦 于 2014-6-29 15:02 编辑

三楼的思路很不错，学习了。

作者: 七弦    时间: 2014-5-27 08:30
西门吹风 发表于 2014-5-27 00:29
今天刚好看完for循环视频，尝试用for循环写了一下，这个数好像不能太大，不然超过long的范围，望高人指正

...

写的很好
作者: 七弦    时间: 2014-5-27 08:33
本帖最后由 七弦 于 2014-6-29 14:59 编辑

21的阶乘已经超过了long的最大
作者: 张百振    时间: 2014-5-27 12:32
只需要求出包含几个2和5，还有几个10的倍数就轻松搞定了不是？想一下，阶乘里只要乘以10，最后肯定多一个0，还有只要包含一个2和5这一对数，就又会多一个0，哈哈哈，多么简单呀，我现在时间太紧了，正在准备面试，要不然就代码写出来了
作者: vampire.007    时间: 2014-5-27 13:00
张百振 发表于 2014-5-26 23:43
个人建议楼上用BigInteger

如果超出了BigInteger呢？这个要想真的很好的解决，我觉得还是要先转化为字符转来解决，毕竟字符串的长度要大于数值型。
作者: 张百振    时间: 2014-5-27 14:28
vampire.007 发表于 2014-5-27 13:00
如果超出了BigInteger呢？这个要想真的很好的解决，我觉得还是要先转化为字符转来解决，毕竟字符串的长度 ...

你想多了吧？10000的阶乘BigInteger都没问题，你还想用String？
作者: pk49800    时间: 2014-5-27 20:23
本帖最后由 pk49800 于 2014-5-28 14:10 编辑
  1. public class ComputeZero {
  2.        
  3.         <p style="line-height: 30px; text-indent: 2em;">public static void main(String[] args){
  4.                 int count = 0;//末尾0的個數
  5.                 int i = 16;//被計算的數，如果太大則需要將計算結果擴充範圍
  6.                 Long sum = 1L;//計算結果
  7.                 while(i!=0){
  8.                         sum = sum*i;
  9.                         i--;
  10.                 }
  11.                 System.out.println(i+"的階乘為："+sum);
  12.                
  13.                 while(sum%5==0){
  14.                         sum = sum/5;
  15.                         count++;
  16.                 }
  17.                
  18.                 System.out.println("末尾包含:"+count+"個0");
  19.                
  20.         }</p>

  22. }
复制代码

這個是求階乘末尾的0，如果階乘分解因式之後包含的N個10（2*5這種也算在內），那這個階乘結果的末尾0就有N個

作者: 铁血丹心    时间: 2014-5-27 21:48
这个题不能硬做乘法啊，发这个大家看懂就会做啦
  1. /**
  2. * 需求：求1到1000乘积的0的个数
  3. * 思路：假设乘积结果是。。。。。000000000，每一个0就相当于乘与10，1到1000的乘积可以等同于将1到1000这些数字完全分解成质数再相乘
  4. * 1=        1*1
  5. * 2=        1*2
  6. * 3=        1*3
  7. * 4=        2*2
  8. * 5=        1*5
  9. * 6=        2*3
  10. * 。
  11. * 。
  12. * 10=        2*5
  13. * 11=        1*11
  14. * 12=        2*3*4
  15. * .
  16. * .
  17. * 15=        3*5
  18. * .
  19. * .
  20. * 20=        2*2*5
  21. * 。
  22. *
  23. * 25=        5*5。
  24. *
  25. * 1000=        2*2*2*5*5*5
  26. * 就是将上面的等号右边的所有数乘起来。我们知道乘积中出现一个10，就会多一个0.而10=2*5，只有2和5乘积才能等于10，其他所有的数的乘积都不等于10。
  27. * 不要说10*20也会有0，要知道我们已经将这些数字完全分解成了质数，所以只要求出上面等号右边能构造成多少个（2*5），明显可以看出2的个数多于5，所以
  28. * 我们只要求出5的个数就是（2*5）的个数，也就是乘积中10的个数，也就是要求的0的个数。
  29. * 怎么求5的个数，楼主的程序我也没看懂。不过我自己想了一种，大家看一下。
  30. * 1.首先只要5的倍数，分解的质数里才会包含5，即
  31. * 5 =        1*5
  32. * 10=        2*5
  33. * 15=         3*5
  34. * 20=        4*5
  35. * .    .
  36. * .        .
  37. * 1000=200*5
  38. * 上面的等号右边我们直观的可以看到已经有200个5,再求1到200分解成5的倍数
  39. *  5 =        1*5
  40. * 10=        2*5
  41. * 15=         3*5
  42. * 20=        4*5
  43. * .    .
  44. * .        .
  45. * 200=        40*5
  46. * 上面上面又有40个5，再求出1到40分解成5的倍数
  47. *  5 =        1*5
  48. * 10=        2*5
  49. * 15=         3*5
  50. * 20=        4*5
  51. * 。
  52. * 40=        8*5
  53. * 上面有8个5，再求1到8分解成5的倍数
  54. * 5=        1*5
  55. * 上面就1个5
  56. * 所以5的个数=200+40+8+1=249
  57. * 步骤：
  58. *
  59. * @author lhy
  60. *
  61. */
  62. public class Test8
  63. {
  64.         public static void main(String[] args)
  65.         {
  66.                 int num=0;//创建变量记录5的个数
  67.                 int z=1000;
  68.                
  69.                 while(z>=5){
  70.                         num = z/5 +num;//第一次是200，第二次是40，第三次是8，其实都是除于5得到的
  71.                         z = z/5;
  72.                 }
  73.                         System.out.print(num);
  74.         }
  75. }
复制代码
作者: woshihq    时间: 2014-5-27 22:01
好难啊！！！！！！！
作者: yinxjfly    时间: 2014-5-28 00:17
学习了！
作者: 七弦    时间: 2014-5-28 07:32
本帖最后由 七弦 于 2014-6-29 15:02 编辑

。。。。。。。。。。。。
作者: 七弦    时间: 2014-5-28 07:34
本帖最后由 七弦 于 2014-6-29 15:00 编辑

。。。。。。。。。。。。。。。。。
作者: 七弦    时间: 2014-5-28 07:44
本帖最后由 七弦 于 2014-6-29 15:00 编辑

。。。。。。。。。。。。。。。。。
作者: 古陵逝烟    时间: 2014-5-28 07:45
前来观摩
作者: 韩长征    时间: 2014-5-28 09:17
本帖最后由 韩长征 于 2014-5-28 09:29 编辑

看了楼上几位的代码和思想，感觉自己的太过于狭隘了。当然也收获不少。
总结一下2*5*10的思想，其实就是在求1-n直接由多少个5的倍数。
当5的倍数为奇数时，表示肯定包含一个2*5.
当5的倍数为偶数时，表示肯定包含一个*10
于是将代码更新，加入了0和负数，负数默认为-1*-2*-3......
  1. public static void getEndZero_3(int x){
  2.                 if(x==0){
  3.                         System.out.println(1);
  4.                 }
  5.                 if(x<0){
  6.                         x=0-x;
  7.                         getEndZero_3(x);
  8.                 }
  9.                 else{
  10.                         int count = 0;
  11.                         for(int y=1;y<=x;y++){
  12.                                 if(y%5==0){
  13.                                         count++;
  14.                                 }
  15.                         }
  16.                         System.out.printlncount);
  17.                 }
  18.         }
复制代码



作者: 师在飞    时间: 2014-5-28 09:38
大家好哇，混个脸熟
作者: wisely    时间: 2014-5-28 09:56
铁血丹心 发表于 2014-5-27 21:48
这个题不能硬做乘法啊，发这个大家看懂就会做啦

只有一个字，顶！
作者: ithmC4    时间: 2014-5-28 10:22
刚重装系统没有Eclipse，用记事本凑合一下，谁帮我运行看看。。。

  1. public class FactorialZeros {

  3.         public static void main(String[] args) {
  4.                 int num = 1000;
  5.                 System.out.println(getZeros(num));
  6.         }

  8.         public static int getZeros(int num) {       
  9.                 int count = 0;
  10.                 for(int i=1; i<=num; i++) {
  11.                         count += getnFive(i);
  12.                 }
  13.                 return count;       
  14.         }

  16.         private static int getnFive(int num) {
  17.                 int count = 0;
  18.                 if((num % 5) == 0) {
  19.                         count++;                         
  20.                         count += getnFive(num / 5);
  21.                 }
  22.                 return count;
  23.         }
  24. }
复制代码
作者: ↘ふ紫铯幽夢    时间: 2014-5-28 11:19
用Bigdecimal
作者: 梦里花-静    时间: 2014-5-28 18:21
貌似见过啊 赞一个 好题
作者: GoodBoy123    时间: 2014-5-28 18:28
看来各位都是高手级别的。
作者: 七弦    时间: 2014-5-29 07:09
韩长征 发表于 2014-5-28 09:17
看了楼上几位的代码和思想，感觉自己的太过于狭隘了。当然也收获不少。
总结一下2*5*10的思想，其实就是在 ...

0是没有阶乘的
作者: Hi天天向上    时间: 2014-5-29 12:14
昨天刚刚做了这道题   呵呵 分享了  不对之处还望指教

public class Test9 {
       
        static int i2 = 0;
        static int j5 = 0;

        public static void main(String[] args) {
               
                int input_number;
                System.out.println("请输入一个整数：");
                Scanner san = new Scanner (System.in);
                input_number = san.nextInt();
               
                for(int i=1;i<=input_number;i++)
                {
                        returnI2(i);
                        returnJ5(i);
                       
                }
                if(i2>=j5)
                {
                        System.out.println(input_number+"的阶乘的结果中包含"+j5+"个0!");
                }
                else
                {
                        System.out.println(input_number+"的阶乘的结果中包含"+i2+"个0!");
                }
        }
       
       
        public static  void  returnI2(int a)
        {
                if(a%2==0)
                {
                        i2++;
                        returnI2 (a/2);
                       
                }
                else
                {
                        i2 = i2;
                }
        }
        public static void  returnJ5(int a)
        {
                if(a%5==0)
                {
                        j5++;
                        returnJ5 (a/5);
                       
                }
                else
                {
                        j5 = j5;
                }
        }
       

}
作者: 冯超    时间: 2014-5-29 16:56
递归·········
作者: 七弦    时间: 2014-5-30 07:50
递归有次数限制，数字过大了就算不出来了。
作者: hengxing0079    时间: 2014-5-30 09:59
Mark，过后来研究研究！
作者: Fightin黑马    时间: 2014-8-28 15:19
vampire.007 发表于 2014-5-27 13:00
如果超出了BigInteger呢？这个要想真的很好的解决，我觉得还是要先转化为字符转来解决，毕竟字符串的长度 ...

BigInteger的长度是可变的,我问老师它的长度最长有多长,老师说取决于你电脑内存的大小,自己做了下试验,反正求10000的阶层没啥问题
作者: doctorsoft    时间: 2015-3-16 14:34
牛...谢谢
作者: 新生小周    时间: 2015-3-16 15:00
学习了，谢谢
作者: bww    时间: 2015-3-16 15:55
看了这么多没有一个正确的答案。蛮力计算的自己去面壁去，你算出来了这样的面试也不会让你过的，没思想；统计2和5的个数，因为5肯定比2少，所以只需要统计5的个数，但是这样的结果只是统计出阶层结果中到底有多少个0，例如20！ 存在0不连续的情况~ 不合题意
作者: bww    时间: 2015-3-17 13:09
bww 发表于 2015-3-16 15:55
看了这么多没有一个正确的答案。蛮力计算的自己去面壁去，你算出来了这样的面试也不会让你过的，没思想；统 ...

昨天被前面的误导了，当然自己思考也不周全，进位的0目前是不可预估的，但是也是不可能进入后续连续的尾数0中的。所以统计5的个数就行了，但是楼上没有写完整的，现给出自己的两种实现（真心不愿意打开myeclipse，所以用C实现）：
int GetCountOf5(int n)
{
    int i, res = 0;
    for(i = 5; i <= n; i += 5)
    {
        int temp = i;
        while(temp%5 == 0)
        {
            res++;
            temp /= 5;
        }
    }
    return res;
}

int GetCountOfFive(int n)
{
    int i, res = 0, maxNum = 0;
    if(n < 5)
        return 0;
    for(i = n; i > n-5; i--)
    {
        if(i%5 == 0)
        {
            maxNum = i;
            break;
        }
    }
    res += maxNum/5;
    res += GetCountOfFive(maxNum/5);
    return res;
}



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