首页 > 代码库 > 编程之美2.2 不要被阶乘吓倒

编程之美2.2 不要被阶乘吓倒

      开始看到这道题目的时候,我还以为是利用字符串表示整型数的思想,后来一看,由于是一个数的阶乘,那么,如果这个数本身就很大,那么,即使是利用字符串表示也是不合理的,所以,看了下这道题的解释,书中给出了一个公式之后就明白了题目的意思。

      首先,我先把函数声明和题目要求贴出来:

/*2.2 不要被阶乘吓倒*/
/*2.2.1 N!的末尾有多少个0*/
int DutCountOf0InFactorialN(int);
/*2.2.2 N!的二进制表示中最低位1的位置*/
int DutPositionOf1InFactorialN(int);
      

      我们想这样一个问题,有一个数N,那么1-N中存在多少个c(c >= 1 && c <= 9)呢?我们可以利用这个公式计算:

1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的

      所以,可以写出如下的代码:

/*2.2.1 N!的末尾有多少个0*/
/*这道题目的解题思想是:2 * 5 = 10,所以,我们只要确定1—N中存在几个5就可以了(因为2有很多)*/
int DutCountOf0InFactorialN(int n)
{
	if (n <= 0)
		return 0;

	int count = 0;

	/*1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的*/
	while (n)
	{
		n += n / 5;
		n /= 5;
	}
	/*返回末尾0的个数*/
	return count;
}

/*2.2.2 N!的二进制表示中最低位1的位置*/
/*二进制中最低位1,所以,需要知道后面存在多少个0,由此,我们只要确定有多少个2就可以了*/
int DutPositionOf1InFactorialN(int n)
{
	if (n <= 0)
		return 0;

	int count = 0;

	/*1-N中存在x的个数的计算公式为:N/x + N/x2 + N/x3 +...,且这个公式最后一定是收敛的*/
	while (n)
	{
		count += n / 2;
		n /= 2;
	}

	return count + 1;
}



编程之美2.2 不要被阶乘吓倒