正数阶乘结尾0的个数-阿里云开发者社区

开发者社区> 云计算> 正文

正数阶乘结尾0的个数

简介:

题目:对任意输入的正整数N,编写C程序求N!的尾部连续0的个数,并指出计算复杂度。如:18!=6402373705728000,尾部连续0的个数是3。  (不用考虑数值超出计算机整数界限的问题)。

刚看到这道题,脑子中一闪而过的肯定是最原始的方法,但是仔细看看题目,不考虑超出计算机整数边界的问题。显然如果数据过大,求阶乘本身就是个复杂的计算,然后再找结果尾数为0的个数。

1、这个问题当然有简便的方法,我们这样思考,结尾0的个数,就是乘积是10的倍数,因子中有多少个10 就有多少个零,10再次分解就可以得到了2x5的组合。也就是阶乘中含有多少个2x5就有多少个尾数为0。

2, 我们在想像以下,在一个阶乘数的因子中,分解质因数之后,2的个数肯定大于5的个数,注意这里是阶乘数所以才可以有这个定论,要是个普通数字结果肯定不是这样的。所以问题又可以简化到求出阶乘数的因子中有多少个为5的因子。

复制代码
/*************************************************************************
    > File Name: zeronum.c
    > Author: Jason
    > Created Time: 2014年06月09日 星期一 23时14分46秒
 ************************************************************************/

#include<stdio.h>

int countFive(int n)
{
    int i, ans = 0;
    for(i = 5; i <= n; i++)
    {
        int j = i;
        while(j%5==0)
        {
            ans++;
            j /= 5;
        }
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",countFive(n));
    return 0;
}
复制代码

 








本文转自NewPanderKing51CTO博客,原文链接: http://www.cnblogs.com/newpanderking/p/3779013.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章