算法小记:n的阶乘(n!)末尾有多少个0

算法小记:n的阶乘(n!)末尾有多少个0

n的阶乘(n!)末尾有多少个0?

代码实现非常简单!!!---- n!的末尾有count个0.

int n; // n!的末尾有count个0.

int count = 0;

for (int i = 0; i < n; i++) {

n /= 5;

count += n;

}

由于在N特别大的时候强行算出N!是不可能的,所以肯定要另找方法解决了。

首先,为什么末尾会有0?因为2 * 5 = 10,0就这么来了。所以只要求出这N!中有多少个2多少个5相乘就好了,由于N! = 1 * 2 * 3 *… * N,而每经过两个数就会有一个2,所以2的出现次数肯定是大于5的,因此只要求有多少个5相乘就好了。

即:n的阶乘(n!)末尾有多少个0? → n的阶乘(n!)含有多少个因子5

因为求的是N的阶乘,而 N! = 1 * 2 * 3 * … * N

那么:这N个数中能被5整除的个数 = N / 5

比如N = 50 ,能被5整除的有 5 10 15 20 25 30 35 40 45 50 共10个,即50/5=10

但别忘了25和50,他们可拆分成55和55*2,也就是他们含有两个因子“5”,以此类推5的m次方会含有m个5作为因子

所以50!末尾有10+2=12个“0”。

所以要求一个数n!末尾有多少个0

可以利用上述循环

int n; // n!的末尾有count个0.

int count = 0;

for (int i = 0; i < n; i++) {

n /= 5;

count += n;

}

第一轮 用 n/5 (整数除法运算)得到1-n中含有因子5的整数的个数。 然后 count += n;

第二轮 再用 n/5 经历过第一轮,实际上此轮相当于 n/25

即含有25作为因子的个数,虽然含有25作为因子的整数含有两个因子5应该加两次

但是含有25的整数必然含有因子5,在第一轮已经计算过一次了,所以这轮每个含有25的整数只需计算一次

第n轮 以此类推,n持续除以5,直到除至含有5的最高次幂的因数。

相关推荐

狗狗发情多少天可以配种?了解最佳配种时间的方法与注意事项
2025毕业生档案邮寄须知
365bet平台网址

2025毕业生档案邮寄须知

📅 07-01 👁️ 2843
八斗学院大数据靠谱么?为什么那么多人都在八斗学院学大数据?