前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >学算法有锤子用? 请问亿的阶乘末尾几个零?

学算法有锤子用? 请问亿的阶乘末尾几个零?

作者头像
zhaoolee
发布2018-04-19 16:08:39
1.2K0
发布2018-04-19 16:08:39
举报
文章被收录于专栏:木子昭的博客木子昭的博客

如果有人问你, 计算机的能力已经这样强了,算法有啥用? 你可以问他,一个亿的阶乘后面有几个零? 这个问题不是常规计算能解决的,即使交给计算机也要花好长时间...

阶乘

阶乘是一种特殊的运算,随着数的增大, 计算量陡增 5! = 5 * 4 * 3 * 2 * 1 = 120 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800 15! = 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1307674368000

对于某数阶乘 末尾有几个零的问题, 稍加分析就会发现, 其实结果后面有几个零,取决于因数能分解出多少个10, 而10的个数取决于分解出的因数5和因数2的个数,而因数2的个数远多于因数5的个数,所以有多少个因数5, 就有多少个零!

  • 5! 有一个因数5;
  • 10! 有两个因数5;
  • 15! 有三个因数5;
  • 20 ! 有四个因数5;
  • 25 ! 有六个因数5;(25 可以分出两个因数5);

把0的个数转化为因数5的个数, 问题就简单了很多, 求100000000!中因数5的个数,交给计算机能在毫秒级完成! 总共有24999999个零

一个亿的阶乘末尾有几个零

class Solution {
    public static long trailingZeros(long n) {
    
        // 本质是求一共有多少个因数5
        
        // 记录5的个数
        long count = 0L;
        
        /*
        temp的两大作用:
        第一: 临时存储"5"的个数(随着每次的循环更新,会越变越少)
        第二: 控制循环(当temp降为0时, 终止循环)
        */ 
        long temp = n / 5;
        
        // 当temp耗尽时, 停止循环
        while (0 != temp){
            
            // 累加上次记录的"5"的个数    
            count += temp;
            // 获得第N 次获取5的个数
            temp = temp / 5;
            
        }
        
        return count;
        
    }
};

class ZeroNum{
    
    public static void main (String[] args) {

        Solution sol = new Solution();
        // 求1亿的阶乘尾部用多少个零 100000000!
        long result = sol.trailingZeros(100000000);

        System.out.println("一亿的阶乘尾部有"+result+"个零");
    }
}

有了很厉害的算法,还需要计算机么?当然需要!如果没有计算机,即便给出阶乘的结果,谁能保证一次就把零的个数,准确无误的数出来?(正确答案是24999999个零)

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.01.27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档