2.2 編程之美--不要被階乘嚇到[zero count of N factorial]，編程之美
2.2 編程之美--不要被階乘嚇到[zero count of N factorial]
[本文鏈接]
http://www.cnblogs.com/hellogiser/p/zero-count-of-N-factorial.html
【題目】
問題1：給定一個整數N，那麼N的階乘N！末尾有多少個0呢？例如：N＝10，N！＝3 628 800，N！的末尾有兩個0。
思路：這個主要是判斷各個數字中5的個數，因為5和偶數相乘以後可以得到10，相當於在後面添加一個0。
問題2：求N！的二進制表示中最低位1的位置。
思路：乍一看，似乎，問題二與問題一沒什麼關系。然而，我們換一個角度思考，二進制中最低位1後面肯定是0，那麼這裡求最低位1的位置，即為求最低位1後面0的個數，而這，就和問題1是一樣的，只不過一個是十進制表，一個是二進制表示。這裡，所有小於N的數中，2的倍數都貢獻一個0，4的倍數再貢獻一個0，以此類推。由於二進制表示其實是以2為基的表示，每出現一個2，末尾才會有一個0，所以只要找到N!中因子2的個數即可。
【代碼】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/7/8
*/
//-----------------------------------------------
// 1 求N! 末尾有多少個0？
//-----------------------------------------------
/* 解法一 計算i（i = 1,2,3..N）的因式分解中5的指數 */
int count(int n)
{
int ret = 0;
int i, j;
for (i = 1; i <= N; i++)
{
j = i;
while (0 == j % 5)
{
ret++;
j /= 5;
}
}
return ret;
}
/* 解法一 優化循環,循環step設置為5 */
int count(int n)
{
int ret = 0;
int i, j;
// 循環step設置為5
for (i = 5; i <= N; i = i + 5)
{
j = i;
while (0 == j % 5)
{
ret++;
j /= 5;
}
}
return ret;
}
/* 解法二 z = [N/5] + [N/(5*5)] + [N/(5*5*5)].... */
/* [N/5]為N中5的個數,[N/(5*5)]為[N/5]中5的個數 */
/* Z為N！中含有質數5的個數 */
int count(int n)
{
int ret = 0;
while (n)
{
ret += N / 5;
N /= 5;
}
return ret;
}
//-----------------------------------------------
// 2 求N!的二進制表示中最低位1的位置
//-----------------------------------------------
/* 2=(10),每出現一個2，1前進1位，如二進制 10*10*10*10 = (10000) */
/* 等於N! 中含有質數因子2的個數加1 */
/* z = [N/2] + [N/(2*2)] + [N/(2*2*2)].... */
int lastone(int n)
{
int ret = 0;
while (n)
{
n >>= 1;
ret += n;
}
return ret;
}
/* 相關題目 判斷n是否為2的方冪 */
bool is2n(int n)
{
return n > 0 && ( 0 == (n & (n - 1)));
}
【參考】
http://blog.csdn.net/eric43/article/details/7570474
http://blog.csdn.net/zcsylj/article/details/6393308
[本文鏈接]
http://www.cnblogs.com/hellogiser/p/zero-count-of-N-factorial.html
