当前位置:Gxlcms > mysql > 【编程之美】2.2不要被阶乘吓到

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

时间:2021-07-01 10:21:17 帮助过:22人阅读

题目: 1:给定一个整数N,那么N的阶乘N!末尾有多少个0?例如N = 10,N!= 3628800,末尾有两个0. 2:求N!的二进制表示中最低位1的位置。 问题一: 题目解析: 这道题如果直接求N!的话也可以,不过万一溢出了怎么办?即使定义longlong类型的也不合适。那


题目:

1:给定一个整数N,那么N的阶乘N!末尾有多少个0?例如N = 10,N!= 3628800,末尾有两个0.

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



问题一:

题目解析:

这道题如果直接求N!的话也可以,不过万一溢出了怎么办?即使定义longlong类型的也不合适。那么就要找寻其中的规律,一般这类题目都可以通过分析,找到一个很简单的方法。


思路一:

我们想想0是怎么来的?乘以10就增加一个0,而10可以通过2*5的来。好了,我们将N!表达式表达出来,看能获得多少个2*5。N! = 2^x * 3^y * 5^z... 由于2比5小,所以x比z要大。所以看N!中有多少个5就可以了。

int Count(int n)
{
    int num = 0;
    for(int i = 1;i < n;++i){
        int j = i;
        while(j%5 == 0){
            num++;
            j /= 5;
        }
    }
}

思路二:

我们可以利用公式Z = [N/5] + [N/(5^2)] + [N/(5^3)] +....

这个公式表达什么意思呢?N/5表示从1-N中有多少个数是5的倍数,那么这些数,每一个都贡献一个5;好了但是对于25会贡献两个,在除以5的时候,已经算进去1个,那么N/(5^2)的时候,看看有多少是25的倍数,也算一下,这时将25中的另一个5给算进去了;同理对于75,当我们N/75的时候,正好把三个5全算进去……通过这个方法,更简化程序的实现。

int Count1(int n)
{
    int num = 0;
    while(n){
        num += n/5; //这种方法更简洁,避免了附设变量
        n = n/5;
    }
    return num;
}


问题二:

说白了,问题2跟问题1是一样的,求N!2的倍数。

思路一:

根据上题的情况,写出如下表达式求表达式N! = 2^x * 3^y * 5^z... 我们要求x的值为多少。也可以通过遍历1-N一个一个求解

int Count2(int n)
{
    int num = 0;
    for(int i =0;i < n;++i){
        int j = i;
        while(j%2 == 0){
            num++;
            j = j/2;
        }
    }
    return num;
}

//当然可以通过位来操作
int Count_2(int n)
{
    int num = 0;
    for(int i =0;i < n;++i){
        int j = i;
        while(!(j & 1)){
            num++;
            j = j >> 1;
        }
    }
    return num;
}

思路二:

类似问题一中的公式,我们也可以写出Z = [N/2] + [N/(2^2)] + [N/(2^3)] +....

int Count3(int n)
{
    int num = 0;
    while(n){
        n = n >> 1;
        num += n;   //这句话写在下面,更好
    }
    return num;
}

思路三:

N!含有质因数2的个数,还等于N减去N的二进制表示中1的数目。——这是一种巧妙的方法,是根据Z = [N/2] + [N/(2^2)] + [N/(2^3)] +....运算得到的,因为除以2,相当于右移一位,对于11011我们有:

Z = 1101 + 110 + 11 + 1 = (1000 + 100 + 1) + (100 + 10) + (10 +1) + 1

= 1111 + 111 + 1 = (10000 - 1) + (1000 - 1) + (10 - 1) + (1 - 1) = 11011 - (N二进制中1的个数)



相关题目:

给定整数n,判断它是否为2的方幂。

(2的方幂为2^X。所以表示为二进制的时候,只有一位为1,那么利用判断二进制的个数的方法来判断: n>0 && ((n && (n-1)) == 0))


人气教程排行