欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于阶乘的面试题总结

程序员文章站 2024-03-15 17:20:00
...

阶乘方面的题一直是我最近不太明白的点,因此我便总结了几个关于阶乘方面的面试题供探讨。

面试题:

一、给定一个整数N,那么N的阶乘N!末尾有多少个0呢?例如:N=10,N!=3 628 800,N!的末尾有两个0。

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

对于第一道题,一般人的思路会是想着求完N!之后再来看,此时就要考虑是不是溢出的问题,但是我们换一个思路想一想,想一下有什么数字相乘可以等于10,我们很容易想到2X5=10。

接着我们可以把N!进行分解质因数(每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。 分解质因数只针对合数。)

所以N!=2x×3y×5z........

可以看到2和5相乘必然会产生一个10,而这个10会在阶乘的末尾添加一个0。那么问题就转化为2x×5z可以产生多少个0,即min(x,z),显然X肯定大于Z(能被2整除的数肯定比5多),最终问题转化为求Z的值-即找出1...N能分解出多少个5。

代码如下:

#include <iostream>
using namespace std;
int countZero(int N) 
{
	int ret = 0, i, j;
	for (i = 1; i <= N; i++)
	{
		j = i;
		while (j % 5 == 0)
		{
			ret++;
			j /= 5;
		}
	}
	return ret;
}
int main()
{
	int x=countZero(10);
	cout << x << endl;
	return 0;
}

实现结果:

关于阶乘的面试题总结

第二题:
我们换一个角度分析,二进制中最低位1的位置厚一位,一定是0,所以我们可以在第一题的基础上加上1代表N!二进制中最低位1的位置。

但是我们第一问是以10进制来表示,第二问是以二进制来表示,所以每当有一个2,我们在末尾才多了一个0,因此只需要找到2的因子的个数即可。

由于N!中质因子2的个数等于N/2 + N/4 + N/8 + N/16 + …因此便可以写程序。

代码如下:

#include <iostream>
using namespace std;
int locateo(int N) 
{
	 int num = 0; 
	 while (N != 0) {
			N >>= 1;
	         num += N;
		}
	 return num + 1;
}
int main()
{
	int x= locateo(10);
	cout << x << endl;
	return 0;
}

运行结果:

关于阶乘的面试题总结