2.2 编程之美--不要被阶乘吓到[zero count of N factorial]

时间:2021-03-31 14:39:24

[本文链接]

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 i, j;

; i <= N; i++)
    {
        j = i;
        )
        {
            ret++;
            j /= ;
        }
    }

return ret;
}

/* 解法一 优化循环,循环step设置为5 */
int count(int n)
{
    ;
    int i, j;

// 循环step设置为5
)
    {
        j = i;
        )
        {
            ret++;
            j /= ;
        }
    }

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)
{
    ;

while (n)
    {
        ret += N / ;
        N /= ;
    }

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)
{
    ;
    while (n)
    {

    ret += n/2;
        n = n/2;
    }

return ret;
}

/* 相关题目 判断n是否为2的方幂 */
bool is2n(int 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
 
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/9/18
*/

// number of zeros of n!
int num_zeros(int n)
{
    // n = 16
    // 5 10 15 20 25
    // 25
)
        ;
    ;
    while(n)
    {
        count += n / ;
        n = n / ;
    }
    return count;
}

int num_zeros2(int n)
{
    // n = 16
    // 5 10 15 20 25
    // 25
)
        ;
    ;
    )
        count += n / i;
    return count;
}

// pos of last one of n! in bit representation
int last_one(int n)
{
    )
        ;
    ;
    while(n)
    {
        count += n / ;
        n = n / ;
    }
    return count;
}

int last_one2(int n)
{
    )
        ;
    ;
    )
        count += n / i;
    return count;
}

【参考】

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