走在架構師的大道上 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×10^m那么N！后面就有m個零。這個問題轉化為將N！進行分解，如N！=2^a×3^b×5^c 很顯然 10=2×5，那么零的個數m=min(a,c), 一個數能夠被2整除的機率比5要大很多因此 m=c，因此轉化為求 c的問題，具體算法如：

publicclass factorial {
2

privatestaticint zeroNum(int n) {
4

int ret = 0;
6

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

int j = i;
10

while (j % 5 == 0) {
12

ret++;
14

j /= 5;
16

}
18

}
20

returnret;
22

}
24

privatestatic BigInteger fac(long n) {
26

BigDecimal a = new BigDecimal(1);
28

BigDecimal b;
30

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

b = new BigDecimal(i);
34

a = a.multiply(b);
36

}
38

return a.toBigInteger();
40

}
42

問題二解法：

我們都知道一個數除以2可以表示為 N>>1，即向右移動一位。這個問題轉化為求 N! 含有2的質因數的個數問題。

staticclass PrimeFactor {
2

publicstaticint primeFactor(int n) {
4

int ret = 0;
6

while (n != 0) {
8

n >>= 1;
10

ret += n;
12

}
14

return ret + 1;
16

}
18

publicstatic String binaryString(int n) {
20

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

}
24

}
26

完整程序：

package org.blogjava.arithmetic;
2

import java.math.BigDecimal;
4

import java.math.BigInteger;
6

/**
8

* @author Jack.Wang
10

* @see http://jack2007.blogjava.net/
12

*/
14

public class factorial {
16

private static int zeroNum(int n) {
18

int ret = 0;
20

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

int j = i;
24

while (j % 5 == 0) {
26

ret++;
28

j /= 5;
30

}
32

}
34

return ret;
36

}
38

private static BigInteger fac(long n) {
40

BigDecimal a = new BigDecimal(1);
42

BigDecimal b;
44

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

b = new BigDecimal(i);
48

a = a.multiply(b);
50

}
52

return a.toBigInteger();
54

}
56

static class PrimeFactor {
58

public static int primeFactor(int n) {
60

int ret = 0;
62

while (n != 0) {
64

n >>= 1;
66

ret += n;
68

}
70

return ret + 1;
72

}
74

public static String binaryString(int n) {
76

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

}
80

}
82

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

System.out.println("12!為" + fac(12) + ",后面零的個數為" + zeroNum(12));
86

System.out.println("12！的二進制為" + PrimeFactor.binaryString(12) + ",1的位置"
88

+ PrimeFactor.primeFactor(12));
90

}
92

/**
94

out:
96

12!為479001600,后面零的個數為2
98

12！的二進制為11100100011001111110000000000,1的位置11
100

101

*/
102

103

}
104

本博客為學習交流用，凡未注明引用的均為本人作品，轉載請注明出處，如有版權問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學習進步。

posted on 2008-10-18 12:05 Jack.Wang 閱讀(4299) 評論(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;
} 回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 計算字符串相似度的簡易算法微軟面試題---階乘問題微軟面試題---求子數組最大乘積問題微軟面試題---求出1的個數之小解 Java中對HashMap的深度分析與比較（轉載初學者筆記）為什么HashCode對于對象是如此的重要?

走在架構師的大道上 Jack.Wang's home

公告

留言簿(26)

我參與的團隊

隨筆分類(232)

隨筆檔案(190)

我的鄰居們

積分與排名

最新評論

閱讀排行榜

評論排行榜

Feedback