学算法有锤子用? 请问亿的阶乘末尾几个零?附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 条评论
登录 后参与评论

相关文章

来自专栏架构说

110. 平衡二叉树

世界分为三条线,两实一虚: 1. 当前时间线: 黑帽威廉时间线,凡是有黑帽威廉的都在当前时间 2. 历史时间线:白帽威廉时间线 (35年前),凡是有白帽威廉的都...

762
来自专栏java一日一条

Java面试题:多继承

招聘和面试对开发经理来说是一个无尽头的工作,虽然有时你可以从HR这边获得一些帮助,但是最后还是得由你来拍板,或者就像另一篇文章“Java 面试题:写一个字符串的...

614
来自专栏落影的专栏

程序员进阶之算法练习(二十六)

前言 金三银四,求职黄金月做算法面试题,热热身子。 正文 1.Chess For Three 题目链接 题目大意: 有三个人A,B,C玩剪刀石头布的游戏,但...

4616
来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十六)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

482
来自专栏木子昭的博客

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

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

3278
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3335
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 7 章: 闭包 vs 对象

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 7 章: 闭包 vs 对象 ...

1897
来自专栏数据结构与算法

UOJ#386. 【UNR #3】鸽子固定器(链表)

如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

541
来自专栏领域驱动设计DDD实战进阶

关于领域对象业务逻辑中条件判断的最佳实践

1174
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十八)

可迭代对象:在之前学习的基础上,可以简单的理解为可以用for循环遍历的,如学过的list tuple dict set str

851

扫码关注云+社区