Java版超大整数阶乘算法代码详解-10,0000级

时间:2022-03-08 07:20:53

当计算超过20以上的阶乘时,阶乘的结果值往往会很大。一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围。如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决。在网上我看到很多用c、c++和c#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章。数组越界,一眼就可以看出程序本身无法运行。转载他人文章的时候,代码倒是仔细看看啊。唉,粗糙。过年了,在家闲来蛋疼,仔细分析分析,用java实现了一个程序计算超大整数阶乘。思想取自网上,由我个人优化和改进。

这个方法采用“数组进位”算法。在超越计算机变量取值范围的情况下,将多位数相乘转化为一位数相乘。如11!=39916800,若需求12的阶乘,则需要将39916800与12相乘,可利用乘法分配率。乘法竖式如下图所示:

Java版超大整数阶乘算法代码详解-10,0000级

使用一个数组来保存阶乘每一位的结果,一个数组元素保存一位数。例如:将11的阶乘的结果399
16800保存到数组的8个元素中,要计算12的阶乘就用每个数组元素中的值去乘以12,并将结果保存到原来的数组元素中。接下来去判断每个数组元素是否需要进位,通过进位操作使数组中的每个元素保存的数都只有一位数,示意图如下:

Java版超大整数阶乘算法代码详解-10,0000级

理论上讲,只要计算机内存空间允许就可以保存任意多位的阶乘结果,不再受变量的取值范围的限制,只受到操作系统的寻址能力和计算机内存的限制。友情提示:如果要求的阶乘数字很大则可以将数组定义为long类型,以避免在计算单位数的乘积时出现溢出的情况。

实现代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class biginteger
{
    /**
     * 计算进位
     * @param bit    数组
     * @param pos 用于判断是否是数组的最高位
     */
    private void carry(int[] bit, int pos)
        {
        int i ,carray = 0;
        for (i = 0 ; i<= pos ;i++)//从0到pos逐位检查是否需要进位
        {
            bit[i] += carray;
            //累加进位
            if(bit[i] <= 9)   //小于9不进位
            {
                carray = 0;
            } else if(bit[i] >9 && i<pos)//大于9,但不是最高位
            {
                carray = bit[i]/10;
                //保存进位值
                bit[i] = bit[i]%10;
                //得到该位的一位数
            } else if(bit[i] > 9 && i >= pos)//大于9,且是最高位
            {
                while(bit[i] > 9)//循环向前进位
                {
                    carray = bit[i]/10;
                    //计算进位值
                    bit[i] = bit[i] % 10;
                    //当前的第一位数
                    i ++ ;
                    bit[i] = carray;
                    //在下一位保存进位值
                }
            }
        }
    }
    /**
     * 大整数阶乘
     * @param biginteger 所计算的大整数
     */
    private void bigfactorial(int biginteger)
        {
        int pos =0;
        //
        int digit;
        //数据长度
        int a , b ;
        int m = 0 ;
        //统计输出位数
        int n = 0 ;
        //统计输出行数
        double sum = 0;
        //阶乘位数
        for (a = 1 ; a <= biginteger ; a ++)//计算阶乘位数
        {
            sum += math.log10(a);
        }
        digit = (int)sum + 1;
        //数据长度
        int[] fact = new int[digit];
        //初始化一个数组
        fact[0] = 1;
        //设个位为 1
        for (a = 2 ; a <= biginteger ; a++ )//将2^biginteger逐个与原来的积相乘
        {
            for (b = digit-1 ; b >= 0 ; b--)//查找最高位{}
            {
                if( fact[b] != 0 )
                                {
                    pos = b ;
                    //记录最高位
                    break;
                }
            }
            for (b = 0; b <= pos ; b++)
                        {
                fact[b] *= a ;
                //每一位与i乘
            }
            carry(fact,pos);
        }
        for (b = digit-1 ; b >= 0 ; b --)
                {
            if(fact[b] != 0)
                        {
                pos = b ;
                //记录最高位
                break;
            }
        }
        system.out.println(biginteger +"阶乘结果为:");
        for (a = pos ; a >= 0 ; a --)//输出计算结果
        {
            system.out.print(fact[a]);
            m++;
            if(m % 5 == 0)
                        {
                system.out.print(" ");
            }
            if(40 == m )
                        {
                system.out.println("");
                m = 0 ;
                n ++;
                if(10 == n )
                                {
                    system.out.print("\n");
                    n = 0;
                }
            }
        }
        system.out.println("\n"+"阶乘共有: "+(pos+1)+" 位");
    }
    public void dobigfactorial(int biginteger)
        {
        int timebegin=(int) system.currenttimemillis();
        this.bigfactorial(biginteger);
        int timefinishi=(int) system.currenttimemillis();
        int time = timefinishi-timebegin;
        system.out.println("计算耗时: " + time +"毫秒" );
    }
    public static void main(string[] args)
        {
        biginteger bi = new biginteger();
        bi.dobigfactorial(100000);
    }
}

计算10,0000的阶乘,显示结果如下:

Java版超大整数阶乘算法代码详解-10,0000级

这样的结果,控制台显然已经无法保存内容了。10万的阶乘有45万位之多,这就相当于一本有45万字的小说一样。对比1000的阶乘结果如下:

Java版超大整数阶乘算法代码详解-10,0000级

控制台可以完整显示。

总结

以上就是本文关于java版超大整数阶乘算法代码详解-10,0000级的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://www.open-open.com/home/space-135360-do-blog-id-9620.html