微软面试题:阶乘问题_求职面试_非技术区_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 非技术区 > 求职面试 > 微软面试题:阶乘问题

微软面试题:阶乘问题

 2010/12/2 10:44:11    程序员俱乐部  我要评论(0)
  • 摘要:阶乘是个很有意思的东西,可能很多朋友看到关于他的计算就怕了,其实没什么,看完下面两个问题您应该有低了。1.给定一个N,求出N!末尾有多少个零,比如N=10,N!=3628800,N!末尾有两个零。2.求N!的二进制表示中最低为1的位置,比如11010010,最低为1的位置为2。问题一解法:在上一个blog中介绍的子数组乘积最大值的问题中,有朋友考虑到溢出的问题,在这个问题中,我们从那些数相乘能得到10这个命题开始思考。比如N!=K×10m那么N!后面就有m个零。这个问题转化为将N
  • 标签:微软面试题

 阶乘是个很有意思的东西,可能很多朋友看到关于他的计算就怕了,其实没什么,看完下面两个问题您应该有低了。

        1.       给定一个 N ,求出N!末尾有多少个零,比如 N=10,N!=3628800,N!末尾有两个零。
2.       N!的二进制表示中最低为1的位置,比如 11010010, 最低为1的位置为2

问题一解法:

    在上一个 blog 中介绍的子数组乘积最大值的问题中,有朋友考虑到溢出的问题,在这个问题中,我们从那些数相乘能得到10这个命题开始思考。比如N=K×10m那么N!后面就有m个零。这个问题转化为将N!进行分解,如N=2a×3b×5c 很显然 10=2×5,那么零的个数m=min(a,c), 一个数能够被2整除的机率比5要大很多因此 m=c,因此转化为求 c的问题,具体算法如:问题二解法:

 1publicclass factorial {
 2

 3    privatestaticint zeroNum(int n) 
{
 4

 5       int ret = 0
;
 6

 7       for (int i = 1; i <= n; i++
{
 8

 9           int j =
 i;
10

11           while (j % 5 == 0
{
12

13              ret++
;
14

15              j /= 5
;
16

17           }

18
19       }

20
21
       returnret;
22

23    }

24
25    privatestatic BigInteger fac(long n) 
{
26

27       BigDecimal a = new BigDecimal(1
);
28

29
       BigDecimal b;
30

31       for (long i = 1; i <= n; i++
{
32

33           b = new
 BigDecimal(i);
34

35           a =
 a.multiply(b);
36

37       }

38
39       return
 a.toBigInteger();
40

41    }

42

我们都知道一个数除以2可以表示为 N>>1,即向右移动一位。这个问题转化为求 N! 含有2的质因数的个数问题。完整程序:

 1    staticclass PrimeFactor {
 2

 3       publicstaticint primeFactor(int n) 
{
 4

 5           int ret = 0
;
 6

 7           while (n != 0
{
 8

 9              n >>= 1
;
10

11              ret +=
 n;
12

13           }

14
15           return ret + 1
;
16

17       }

18
19       publicstatic String binaryString(int n) 
{
20

21           return
 Integer.toBinaryString(fac(n).intValue());
22

23       }

24
25    }

26

 

  1package org.blogjava.arithmetic;
  2

  3import
 java.math.BigDecimal;
  4

  5import
 java.math.BigInteger;
  6

  7
/**
  8
  9 * @author
 Jack.Wang
 10

 11 * @see ORATION: underline">http://jack2007.blogjava.net/

 12
 13 */

 14
 15public class factorial 
{
 16

 17       private static int zeroNum(int n) 
{
 18

 19              int ret = 0
;
 20

 21              for (int i = 1; i <= n; i++
{
 22

 23                     int j =
 i;
 24

 25                     while (j % 5 == 0
{
 26

 27                            ret++
;
 28

 29                            j /= 5
;
 30

 31                     }

 32
 33              }

 34
 35              return
 ret;
 36

 37       }

 38
 39       private static BigInteger fac(long n) 
{
 40

 41              BigDecimal a = new BigDecimal(1
);
 42

 43
              BigDecimal b;
 44

 45              for (long i = 1; i <= n; i++
{
 46

 47                     b = new
 BigDecimal(i);
 48

 49                     a =
 a.multiply(b);
 50

 51              }

 52
 53              return
 a.toBigInteger();
 54

 55       }

 56
 57       static class PrimeFactor 
{
 58

 59              public static int primeFactor(int n) 
{
 60

 61                     int ret = 0
;
 62

 63                     while (n != 0
{
 64

 65                            n >>= 1
;
 66

 67                            ret +=
 n;
 68

 69                     }

 70
 71                     return ret + 1
;
 72

 73              }

 74
 75              public static String binaryString(int n) 
{
 76

 77                     return
 Integer.toBinaryString(fac(n).intValue());
 78

 79              }

 80
 81       }

 82
 83       public static void main(String[] args) 
{
 84

 85              System.out.println("12!为" + fac(12+ ",后面零的个数为" + zeroNum(12
));
 86

 87              System.out.println("12!的二进制为" + PrimeFactor.binaryString(12+ ",1的位置"

 88
 89                            + PrimeFactor.primeFactor(12
));
 90

 91       }

 92
 93       
/**
 94
 95
        out: 
 96

 97
        12!为479001600,后面零的个数为2
 98

 99
        12!的二进制为11100100011001111110000000000,1的位置11
100

101        */

102
103}

104


本文来自:http://www.blogjava.net/Jack2007/archive/2008/10/18/235152.html

发表评论
用户名: 匿名