不要被阶乘吓倒

阶乘是个很有意思的函数，我们来看看两个跟阶乘相关的问题。

1、给定一个整数N，那么N的阶乘N!末尾有多少个0呢？例如：N=10，N! = 3628800，末尾就有两个0

2、求N! 的二进制表示中最低位1的位置

 

我们先分析第一个问题

我们发现0的个数，就是10的个数，而10是由2跟5组成的，但是，5的个数明显少于2，所以问题就转换为求5的个数。

#include <iostream>
using namespace std;
// O(nlogn)，思路：找0的个数，就是找10的个数，就是2*5的个数，2比5多，所以就是找5的个数，首先找到5的倍数，再判断这些数里面有多少个5
int numOfZeros1(int n)
{
    //i从1开始，当n为26时，那么i就是1,2,3,4,5
    //j就是5*i，所以对于的j就是5,10,15,20,25，第二个while循环找的就是j中有多少个5，像数字25，就有2个5
    //count表示的5的个数，即0的个数
    int i, j, count;
    i = 1;
    count = 0;
    while (5 * i <= n)
    {
        j = 5 * i;
        while (j % 5 == 0)
        {
            count++;
            j = j / 5;
        }
        i++;
    }
    return count;
}
// o(logn)，从时间复杂度上来说，优化的多。思路：n=26时，0的个数就是[26/25]+[26/5]=1+5=6
int numOfZeros2(int n)
{
    int i, count;
    i = 0;
    count = 0;
    while (n / 5)
    {
        count += n / 5;
        n /= 5;
    }
    return count;
}
int main()
{
    int n;
    n = 125;
    //test
    cout<<numOfZeros1(n)<<endl;
    cout<<numOfZeros2(n)<<endl;
    system("pause");
    return 0;
}

 

第二个问题的解答如下，分析也在代码中了

#include <iostream>
using namespace std;
// o(logn)，在二进制中，乘以2就表示多一个0，所以，1最低位的位置其实就是2个个数+1
int indexOfOne(int n)
{
    int i, count;
    i = 0;
    count = 0;
    //这里进行了一点点调整，更简洁了，可对比上面的代码，看看哪里调整了
    while (n)
    {
        //注意除以2，都可以用右移来标识哦！！
        n = n >> 1;
        count += n;
    }
    return count + 1;
}
int main()
{
    int n;
    n = 3;
    //test
    cout<<indexOfOne(n)<<endl;
    system("pause");
    return 0;
}