首页 > 其他 > 详细

求N的阶乘N!中末尾0的个数

时间:2016-01-26 21:48:08      阅读:174      评论:0      收藏:0      [点我收藏+]

有道问题是这样的:给定一个正整数N,那么N的阶乘N!末尾中有多少个0呢?例如:N=10,N!=3628800,则N!的末尾有两个0;

直接上干货,算法思想如下:

对于任意一个正整数N!,都可以化为N!= (2^X)  * (3^Y)* (5^Z)......的形式,要求得末尾0的个数只需求得min(X, Z)即可,

由于是求N!,则X >= Z; 即公约数5出现的频率小于等于2出现的频率,即Z=min(X, Z),即出现0的个数等于公约数5出现的次数;

源码如下:

方法一:

#include <stdio.h>
int main()
{
    int N;                      
    int sum = 0; 
    scanf("%d", &N);          // 输入N
    for(int i = 1; i <= N; i++)
    {
        int j = i;
        while(0 == j % 5)
        {
            sum++;            // 统计公约数5出现的频次
            j /= 5;
        }
    }

    printf("%d\n", sum);

    return 0;
}

  方法二:

#include <stdio.h>
int main()
{
	int N;
	int sum = 0;
	scanf("%d", &N);
	while(N)
	{
		sum += N / 5;
		N /= 5;
	}
	printf("%d\n", sum);

	return 0;
}

  

 

求N的阶乘N!中末尾0的个数

原文:http://www.cnblogs.com/wkx12/p/5161463.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!