Java Long类型阶乘计算-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

Java Long类型阶乘计算

2016-03-10 18:08:40 1913 1

问题描述:
n! <= 2^63-1 , 求最大的n.
问题:
如果不用java自带的 Long.MAX_VALUE,这个值,如何表示Long类型的最大值,我的表示方法为啥不对?
我的代码如何修改才能得到正确的值呢?(因为我观察到factorial这个变量从某一刻开始变成0,可能那个时刻就已经求到了最大的n? long类型的factorial范围不够用了?)
有什么优化的算法呢?

 /**
     * calculate the max value of n that n! < maxValueOf(Long)
     * long 8 bytes
     * @return max n
     */
    private static int findMax() {
        long maxLongValue = Long.MAX_VALUE;//(2<<(8*8-1))-1;
        System.out.println(maxLongValue);
        // n! <= 2^63-1, we recommend algorithm
        int n = 5;


        while(true){
            long factorial =n; //watch out here long
            int origin = n;
            while(n>1){
                factorial *= (n-1);
                n--;
            }
            System.out.println("--------" + factorial);
            n = origin;
            if((factorial+1) <= maxLongValue){
                n++;
                System.out.println("n="+ n +" factorial="+factorial);
            }else{
                n--;
                return n;
            }
        }
    }

结果

  /**
     * calculate the max value of n that n! < maxValueOf(Long)
     * long 8 bytes
     * @return max n
     */
    private static int findMax() {
        long maxLongValue = (1L<<(8*8-1))-1;
        System.out.println(maxLongValue);
        // n! <= 2^63-1, we recommend algorithm
        int n = 5;

        long lastFactorial = n;
        
        while(true) {
            if (n == 5) {
                long firstFactorial = n;//watch out here long
                int origin = n;
                while (n > 1) {
                    firstFactorial = firstFactorial * (n - 1);
                    n--;
                }
                lastFactorial = firstFactorial;
                n = origin + 1;
            } else {
                //we do worry about currentFactorial*(n-1) cus we never let a variable store it
                //in fact we have to worry about currentFactorial*(n-1)
                if (lastFactorial <= (maxLongValue/n)) {
                    if(n==17){
                        System.out.println("here---for debug only");
                    }
                    lastFactorial = lastFactorial * n;
                    n++;
                } else {
                    return n - 1;
                }
            }
        }
    }

结果n=20;

取消 提交回答
全部回答(1)
  • 蛮大人123
    2019-07-17 18:58:06

    (1L << 63)-1 注意必须写1L(long字面量), 不能写1(int字面量)
    每个long都一定不大于maxLongValue的, 所以不能用这个来判断溢出. 在已知n!没溢出时可以用(n+1)! / (n+1) == n!来判断.
    如果你只需要n (不要阶乘的精确值), 可以用斯特林公式求n!的近似. 但是因为这个搜索范围太小..未必比从1开始逐个算要快.

    0 0
相关问答

40

回答

[@徐雷frank][¥20]什么是JAVA的平台无关性

大河人家 2018-10-29 23:55:20 144714浏览量 回答数 40

162

回答

惊喜翻倍:免费ECS+免费环境配置~!(ECS免费体验6个月活动3月31日结束)

豆妹 2014-10-29 17:52:21 226137浏览量 回答数 162

8

回答

OceanBase 使用动画(持续更新)

mq4096 2019-02-20 17:16:36 337002浏览量 回答数 8

13

回答

[@饭娱咖啡][¥20]我想知道 Java 关于引用那一块的知识

心意乱 2018-10-31 18:44:12 142455浏览量 回答数 13

110

回答

OSS存储服务-客户端工具

newegg11 2012-05-17 15:37:18 295540浏览量 回答数 110

22

回答

爬虫数据管理【问答合集】

我是管理员 2018-08-10 16:37:41 147231浏览量 回答数 22

18

回答

阿里云开放端口权限

xcxx 2016-07-20 15:03:33 646768浏览量 回答数 18

31

回答

[@倚贤][¥20]刚学完html/css/js的新手学习servlet、jsp需要注意哪些问题?

弗洛伊德6 2018-10-27 21:52:43 146035浏览量 回答数 31

42

回答

【精品问答集锦】Python热门问题

小六码奴 2019-05-30 15:27:34 136956浏览量 回答数 42

10

回答

[@墨玖tao][¥20]为什么流式处理框架都是 java 写成的,JVM 是不是在流和批存在着特殊优势。还有分布式资源调度,感觉Mesos 的成长速度跟不上 Yarn。这是为什么?

管理贝贝 2018-10-23 13:18:03 136465浏览量 回答数 10
+关注
蛮大人123
我说我不帅他们就打我,还说我虚伪
0
文章
7733
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载