[c语言中n的阶乘怎么表示]数的阶乘c语言表示!

对于阶乘这个概念相信很多人都不陌生，但是在计算机领域中，计算一个整形数的阶乘无疑会使得这个数疯狂的进行增长，如果溢出了如何处理这个数据所带来的操作呢？今天我就见到了一道关于阶乘的面试题，感觉比较容易踩坑就写下来分享了~~~

1、给定一个整数N，那么N的阶乘N！末尾有多少个0呢？例如：N＝10，N！＝3 628 800，N！的末尾有两个0。

如果看到这道题你是先把N!计算出来再求末尾0的个数，那仫恭喜你踩坑了，我开始也是这仫做的。

代码实现如下：

int GetZeroCount1(int N)

{

//先计算阶乘再求0的个数，容易溢出

if (N == 0 || N == 1) //0!=1 1!=1，必然没有0所以返回0

return 0;

int count = 0;

int Mul = 1;

for (int i = 2; i <= N; i++)

{

Mul *= i;

}

while (Mul)

{

if (Mul%10 == 0)

{

count++;

}

Mul /= 10;

}

return count;

}

是不是感觉这段代码low极了，如果给你一个特别大的N你先把N!计算出来，那仫计算机能不能存储下来还是个问题？又如何去找末尾0的个数呢？

【解法一】

如果我们从哪些数相乘可以得到10这个角度来思考这个问题，这个问题就变得简单了。

首先，我们可以将N!进行转化N!=K*(10*M)，这里的K是不可以被10整除的，也就是说N!末尾有M个0，那仫N!就只和M有关系了；

然后我们再将N!进行以下质因数分解：N!=(2^x)*(3^y)*(5^z)…，因为10=2*5。所以可以转化为M只和x，z有关系M=Min{x,z}，因为能被2整除的数出现的频率比能被5整除的数高的多(x出现的次数多余z出现的次数)；

最终这道题可以转化为求z的值，就可以求出N!末尾0的个数。

代码实现如下：

int GetZeroCount2(int N)

{

//转化为求5的倍数的个数

//N!=K*(10*M)，K是不能被10整除的，该题目转化为求M的大小

//分解N!=(2*X)*(3*Y)*(5*Z)，因为2*5=10，所以又可以转化为求X和Z中较小的那个值

//M=Min{X,Z}，因为一个数据中2的倍数出现的次数比较多，最终转化为求5的倍数的个数

int count = 0;

if (N == 0 || N == 1)

return 0;

for (int i = 1; i <= N; i++)

{

int j = i;

while (j % 5 == 0)

{

count++;

j /= 5;

}

}

return count;

}

【解法二】

先给出一个公式z=[N/5]+[N/5^2]+[N/5^3]+…，解法二是基于解法一理解的，不要担心这种解法会死循环，由上述N!=K*(10*M)公式可知，始终存在一个不能被10整除的K，使得5^K>0，故[N/5^K]=0；

在公式中[N/5]表示不大于N的数中5的倍数贡献一个5，而[N/5^2]表示不大于N的数中5^2的倍数再贡献一个5。

代码实现如下：

int GetZeroCount3(int N)

{

int count = 0;

if (N == 0 || N == 1)

return 0;

while (N)

{

count += N / 5;

N /= 5;

}

return count;

}

【解法三】

先存储部分数据再统计0出现的次数，如果大于MAX则只保存末尾５位数字即可。

const int MAX = 100000;

int GetZeroCount4(int N)

{

//先存储一部分数据

int sum = 1;

int count = 0;

if (N == 0 || N == 1)

return 0;

for (int i = N; i >= 1; i–)

{

sum *= i;

while (sum % 10 == 0) //统计0出现的次数

{

sum /= 10;

count++;

}

if (sum >= MAX) //如果sum过大则只存储后五位

{

sum %= MAX;

}

}

while (sum % 10 == 0) //统计0出现的次数

{

sum /= 10;

count++;

}

return count;

}

2、求N！的二进制表示中最低位1的位置。例如N=5，N!=5!=120，120的二进制表示为0111 1000，它的二进制中最低位1的位置是第四位。

当然了这道问题如果先求N!的值，也会和第一题那样出现类似的问题，溢出了怎仫办？那仫只能转化了~~~

我们知道的是一个数除于2等价于右移一位)，有了上面那个概念就可以将第二题转化啦！！！可以等价于为求N!中质因数2的个数。

代码实现如下：

int GetLowest1(int N)

{

int pos = 1; //从倒数第一位开始

while (N)

{

N >>= 1;

pos += N;

}

return pos;

}

当然了关于阶乘的题目很多，今天就分享这几个吧！！！