【编程之美】 2.2 不要被阶乘吓到

发表于

描述
问题1:给定要给整数n，求n!中末尾0的个数
问题2:给定整数n，求n!中最低位1的位置

问题1
分析一下，就是统计含有5的个数,于是有代码:
emmm,算法的时间复杂度为O(n*log2(k))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countFac0(int n){
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int k = i;
        while (k) {
            if (k % 5 == 0) {
                sum++;
                k /= 5;
            }
            break;
        }
    }
    return sum;
}

书中改进后的代码,显然更优，也理解起来更加费力
先整体除以5，求数目，再求25的倍数，以此类推

1
2
3
4
5
6
7
8
int countFac2(int n) {
    int sum = 0;
    while (n) {
        sum += n / 5;
        n /= 5;
    }
    return sum;
}

问题二
关键要转换成求这个阶乘数的质因数2的个数，加个1就好。
二进制数，末尾为0=>为偶数，那就看有多少个0，也就是能除以多少个2，题目要求1的位置，于是要加个1。

类似问题一的二解法,本问还可以计算1的个数，用N减得到的即为质因数的个数。