学算法有锤子用? 请问亿的阶乘末尾几个零?附java代码实现

如果有人问你, 计算机的能力已经这样强了,算法有啥用?

你可以问他,一个亿的阶乘后面有几个零? 这个问题不是常规计算能解决的,即使交给计算机也要花好长时间...

阶乘函数

阶乘是一种特殊的运算,随着数的增大, 计算量陡增

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个零)

原文链接:https://www.jianshu.com/p/c58d194d3136

原文发布于微信公众号 - java工会(javagonghui)

原文发表时间:2018-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

3575
来自专栏小樱的经验随笔

单表代替密码原理及算法实现

    要了解单表替代密码就得先了解替代密码,在这里我就做一下简单的介绍:       替代是古典密码中用到的最基本的处理技巧之一 。       替代密码是指...

5016
来自专栏WOLFRAM

九宫格数独游戏

1948
来自专栏章鱼的慢慢技术路

牛课堂算法直播题目

2708
来自专栏北京马哥教育

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

2870
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

4649
来自专栏cs

Mathematica学习笔记

放假了,近来无事,就复习了一下mathematica相关知识点。已经玩了很多东西,不过大概还是很熟悉。 Mathematica(我简称mma),可以通过交互方...

5126
来自专栏机器学习入门

POJ 刷题系列:1083. Moving Tables

POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

21110
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之从1到n中出现1的次数(九度OJ1373)

题目描述: 亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的...

18910
来自专栏用户2442861的专栏

百度 阿里 华为 腾讯 谷歌面试笔试题及解析

点评:其余题目请参见:http://blog.csdn.net/doc_sgl/article/details/11695671。 2、一个有10亿条记录...

4033

扫码关注云+社区