编程之美-不要被阶乘吓到

﹏ヽ暗。殇╰゛Y 2022-08-06 14:08 112阅读 0赞

题目

1、给定一个整数N，那么阶乘N!末尾有多少个0呢？

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

先来看怎么计算阶乘，当然可以是循环，也可以是递归，上代码：

public long factorial1(int n) {
        	long sum = 1;
        	for (int i = 1; i <= n; i++) {
        		sum *= i;
        	}
        	return sum;
        }
        
        public long factorial2(int n) {
        	if (n == 1) {
        		return n;
        	}
        	return n*factorial2(n-1);
        }

两种方法都比较简单。但是很明显如果本题也这样计算的话，明显long型会溢出，并且时间复杂度也比较高。那怎么办？

问题1  
解法一

N个自然数相乘，结尾0的个数，依赖有多少个10相乘，而多少个10则依赖与因子中2的个数和5的个数，而对于连续的自然数来说，2出现的频率比5高的多，所以最终只需要计算出因子中5的个数，即为答案。

public int trailingZeroes1(int n) {
        	int count = 0;
        	for (int i = 1; i <= n; i++) {
        		int temp = i;
        		while (temp%5 == 0) {
        			count++;
        			temp /= 5;
        		}
        	}
        	return count;
        }

当然你可以优化，把i的初始值设置为5，每次递增也为5。但是还是不够高效

解法二

令f(x)表示正整数x末尾所含有的“0”的个数，则有：  
 当0 < n < 5时，f(n!) = 0;  
 当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）

数据功底比较好的可以去证明一下，我就不证明了，上代码：

public int trailingZeroes2(int n) {
        	return n == 0 ? 0 : n / 5 + trailingZeroes2(n / 5);
        }

就是这么简练。  
解法三

还是计算5的个数:

公式：Z = \[N/5\] +\[N/52\] +\[N/53\] + …（不用担心这会是一个无穷的运算，因为总存在一个K，使得5K > N，\[N/5K\]=0。）

公式中，\[N/5\]表示不大于N的数中5的倍数贡献一个5，\[N/52\]表示不大于N的数中52的倍数再贡献一个5，……代码如下:

public int trailingZeroes3(int n) {
        	int count = 0;
        	while (n != 0) {
        		count += n/5;
        		n /= 5;
        	}
        	return count;
        }

问题2

要求的是N！的二进制表示中最低位1的位置。给定一个整数N，求N！二进制表示的最低位1在第几位？例如：给定N = 3，N！= 6，那么N！的二进制表示（1 010）的最低位1在第二位。

为了得到更好的解法，首先要对题目进行一下转化。  
首先来看一下一个二进制数除以2的计算过程和结果是怎样的。  
把一个二进制数除以2，实际过程如下：  
判断最后一个二进制位是否为0，若为0，则将此二进制数右移一位，即为商值（为什么）；反之，若为1，则说明这个二进制数是奇数，无法被2整除（这又是为什么）。  
所以，这个问题实际上等同于求N！含有质因数2的个数。即答案等于N！含有质因数2的个数加1。

public int lowestOne1(int n) {
        	int count = 0;
        	while (n != 0) {
        		n >>= 1;
        		count += n;
        	}
        	return count;
        }