微软面试题-凯发k8网页登录

java, c , linux c, c#.net 技术,软件架构,领域建模,it 项目管理

凯发k8网页登录-凯发天生赢家一触即发官网 凯发k8网页登录首页 新随笔 联系 聚合 管理
  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



本博客为学习交流用，凡未注明引用的均为本人作品，转载请注明出处，如有凯发k8网页登录的版权问题请及时通知。由于博客时间仓促，错误之处敬请谅解，有任何意见可给我留言，愿共同学习进步。
posted on 2008-10-18 12:05 jack.wang 阅读(4182) 评论(1)  编辑  收藏 所属分类: 数学&算法
# re: 微软面试题---阶乘问题 2008-10-22 17:01
private static int zeronum(int n){
int ret = 0;

while(n >= 5){
ret = n/5;
n = n / 5;
}
return ret;
}  回复  
  


只有注册用户后才能发表评论。
网站导航:
              
 
网站地图