走在架构师的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技术,软件架构,领域建模,IT 项目管理 Dict.CN 在线词典, 英语学习, 在线翻译

BlogJava 首页 新随笔 联系 聚合 管理
  195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks
 阶乘是个很有意思的东西,可能很多朋友看到关于他的计算就怕了,其实没什么,看完下面两个问题您应该有低了。

        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 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




本博客为学习交流用,凡未注明引用的均为本人作品,转载请注明出处,如有版权问题请及时通知。由于博客时间仓促,错误之处敬请谅解,有任何意见可给我留言,愿共同学习进步。
posted on 2008-10-18 12:05 Jack.Wang 阅读(3930) 评论(1)  编辑  收藏 所属分类: 数学&算法

Feedback

# re: 微软面试题---阶乘问题 2008-10-22 17:01 icalm
private static int zeroNum(int n){
int ret = 0;

while(n >= 5){
ret += n/5;
n = n / 5;
}
return ret;
}  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: