亚洲最大的成人网,亚洲AV无码AV吞精久久,亚洲av成人一区二区三区观看在线

階乘是個(gè)很有意思的東西，可能很多朋友看到關(guān)于他的計(jì)算就怕了，其實(shí)沒(méi)什么，看完下面兩個(gè)問(wèn)題您應(yīng)該有低了。

1. 給定一個(gè) N ，求出N！末尾有多少個(gè)零，比如 N=10,N!=3628800,N!末尾有兩個(gè)零。
2. 求N!的二進(jìn)制表示中最低為1的位置，比如 11010010, 最低為1的位置為2。

問(wèn)題一解法：

在上一個(gè) blog 中介紹的子數(shù)組乘積最大值的問(wèn)題中，有朋友考慮到溢出的問(wèn)題，在這個(gè)問(wèn)題中，我們從那些數(shù)相乘能得到10這個(gè)命題開(kāi)始思考。比如N！=K×10^m那么N！后面就有m個(gè)零。這個(gè)問(wèn)題轉(zhuǎn)化為將N！進(jìn)行分解，如N！=2^a×3^b×5^c 很顯然 10=2×5，那么零的個(gè)數(shù)m=min(a,c), 一個(gè)數(shù)能夠被2整除的機(jī)率比5要大很多因此 m=c，因此轉(zhuǎn)化為求 c的問(wèn)題，具體算法如：

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

問(wèn)題二解法：

我們都知道一個(gè)數(shù)除以2可以表示為 N>>1，即向右移動(dòng)一位。這個(gè)問(wèn)題轉(zhuǎn)化為求 N! 含有2的質(zhì)因數(shù)的個(gè)數(shù)問(wèn)題。

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) + ",后面零的個(gè)數(shù)為" + zeroNum(12));
86

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

+ PrimeFactor.primeFactor(12));
90

}
92

/**
94

out:
96

12!為479001600,后面零的個(gè)數(shù)為2
98

12！的二進(jìn)制為11100100011001111110000000000,1的位置11
100

101

*/
102

103

}
104

本博客為學(xué)習(xí)交流用，凡未注明引用的均為本人作品，轉(zhuǎn)載請(qǐng)注明出處，如有版權(quán)問(wèn)題請(qǐng)及時(shí)通知。由于博客時(shí)間倉(cāng)促，錯(cuò)誤之處敬請(qǐng)諒解，有任何意見(jiàn)可給我留言，愿共同學(xué)習(xí)進(jìn)步。

posted on 2008-10-18 12:05 Jack.Wang 閱讀(4301) 評(píng)論(1) 編輯收藏所屬分類: 數(shù)學(xué)&算法

Feedback

# re: 微軟面試題---階乘問(wèn)題 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;
} 回復(fù) 更多評(píng)論

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

走在架構(gòu)師的大道上 Jack.Wang's home

公告

留言簿(26)

我參與的團(tuán)隊(duì)

隨筆分類(232)

隨筆檔案(190)

我的鄰居們

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

Feedback