Java 中大数的阶乘

2024 年 9 月 10 日 | 阅读 7 分钟

我们已经讨论过数字的阶乘。然而，我们仍然需要单独讨论大数的阶乘。这是因为一个人不能用计算小数阶乘的方法来计算大数的阶乘。因此，在本节中，我们将讨论如何在 Java 中查找大数的阶乘。让我们通过一个例子来理解。

示例

数字 10 的阶乘是

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800

数字 3628800 可以轻松存储。但是，问题是，如果不是 10，而是要计算 110 的阶乘呢？110 的阶乘是

110! = 110 x 109 x 108 x 107 x 106 x … x 3 x 2 x 1 = 15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000</p>

这里的问题是如何存储数字 110 的阶乘，它包含 179 位数字？

算法

步骤 1：创建一个大小为 maximum 的数组“result[]”，其中 maximum 是输出中存在的最大位数。

步骤 2：将数组“result[]”中存储的值初始化为 1，并将 result[] 数组的大小 resultSize 初始化为 1。

步骤 3：对从 y = 2 到 num 的所有数字执行以下操作。

……i) 将 y 与 result[] 相乘，并更新 result[] 和 resultSize 以保持乘法结果。

上述算法强调了基本学校数学的应用。其思想是通过分别选取两个数字的每一位来相乘，并将进位传递到下一个两位数的乘法中。让我们通过一个例子来理解。

假设我们必须将 9786 乘以 10。那么，我们将执行如下乘法。

将数字 9786 存储在数组中，如下所示

result[] = {6, 8, 7, 9}

y = 10

将进位初始化为 c = 0。

对 j = 0 到 resultSize - 1 执行以下操作

....a) 找到 result[j] * y + v 的值。设该值为 product。

....b) 通过将 product 的最后一位存储在其中来更新 result[j]。

....c) 通过将剩余的位数保留在进位中来更新进位。

j = 0, product = result[0] * y + c = 6 * 10 + 0 = 60。

result[0] = 0, c = 6

j = 1, product = result[1] * y + c = 8 * 10 + 6 = 86

result [1] = 6, c = 8

j = 2, product = result[2] * y + c = 7 * 10 + 8 = 78

result [2] = 8, c = 7

j = 3, product = result[3] * y + c = 9 * 10 + 7 = 97

result [3] = 7, c = 9

现在，将进位的所有位数放入 result[]，并将 resultSize 增加进位中的位数。

因此，

result[4] = c = 9

因此，结果数组变为

result[] = {0, 6, 8, 7, 9}

现在，我们所要做的就是按相反的顺序打印结果数组。因此，当我们将 9786 乘以 10 时，得到 97860。

注意：对于数字 9786，我们以相反的顺序将其数字存储在结果数组中。这是因为如果我们以数字中出现的相同顺序存储数字，那么在不使用额外空间的情况下更新 result[] 将变得困难。

实施

让我们看看上述算法的实现。

使用数组

文件名：LargeNumFact.java

public class LargeNumFact
{
// assuming that the digits of the factorial of a
// number can not exceed 400.
// If the digits of the output, which is the factorial 
// of a large number exceeds 400, then change the 
// number accordingly.
int result[] = new int[400];

// a method that finds the factorial of
// the large numbers and then 
// returns the number of digits present in the factorial
public int factorial(int num)
{
// Initialize the result
result[0] = 1;
int resultSize = 1;

// Applying the simple formula of factorial 
// f! = 1 x 2 x 3 x 4 ... x f
for (int f = 2; f <= num; f++)
{
resultSize = multiply(f, result, resultSize);
}

return resultSize;
}

// The following method multiplies x with the number
// represented by the result[] array. resultSize is the size of the result[] array 
// or the number of digits resent in the number that is represented by result[].
// The method uses the basic school mathematics for
// the multiplication. The method may increase the value of resultSize
// and returns a new value of the resultSize
static int multiply(int y, int result[], int resultSize)
{
int c = 0; // Initializing the carry
// performing the basic multiplication
// and updating the result array
for (int j = 0; j < resultSize; j++)
{
int product = result[j] * y + c;
result[j] = product % 10; // Storing the last digit of
		// 'product' in the result[] array
c = product / 10; // Put the rest in c
}
// Putting the carry in the result[] array and increase the result size resultSize
while (c != 0)
{
result[resultSize] = c % 10;
c = c / 10;
resultSize = resultSize + 1;
}
return resultSize;
}
// main method
public static void main(String argvs[])
{
int num = 110;
// creating an object of the class LargeNumFact
LargeNumFact obj = new LargeNumFact();
// storing the result of the method factorial()
int resSize = obj.factorial(num);
System.out.println("The factorial of the number " + num + " is: ");
// printing the result
for(int j = resSize - 1; j >= 0; j--)
{
System.out.print(obj.result[j]);
}
}
}

输出

The factorial of the number 110 is: 
15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000

使用 LinkedList

除了数组之外，还可以使用链表来计算大数的阶乘。使用链表的优点是链表不会占用任何额外空间。这是因为与数组不同，我们可以根据需要分配和取消分配内存。

文件名：LargeNumFact1.java

// instantiating this class
// will create a node of the linked list
class LinkedListNode
{
int val;
LinkedListNode next;

// constructor of the class LinkedListNode
LinkedListNode(int num)
{
// initializing the fields
this.val = num;
this.next = null;
}
}
public class LargeNumFact1
{
void Multiply(LinkedListNode h, int n)
{
    // a temp variable for keeping the tail
    LinkedListNode temp = h;
    LinkedListNode prvNode = h; 
    int c = 0;
    while (temp != null) 
    {
        int val = temp.val * n + c;       
        // storing the last digit
        temp.val = val % 10; 
        c = val / 10;
        prvNode = temp;
        // Moving temp by 1 prvNode will
        // now denote temp
        temp = temp.next; 
    }
    // If carry c is greater than 0,
    // then we have to create another node
    // for it.
    while (c != 0) 
    {
        prvNode.next = new LinkedListNode((int)(c % 10));
        c /= 10;
        prvNode = prvNode.next;
    }
}

void display(LinkedListNode h)
{
    // Using the tail recursion
    
    // handling the base case
    if (h == null)
    {
        return;
    }
    display(h.next);
    
    // recursively printing the 
    // linked list in the reverse order
    System.out.print(h.val); 
}
// main method
public static void main(String argvs[])
{
int num = 110;
// creating an object of the class LargeNumFact1
LargeNumFact1 obj1 = new LargeNumFact1();
System.out.println("The factorial of the number " + num + " is: ");

    // Create the first node of the linked list
    // and its value is 1
    LinkedListNode obj = new LinkedListNode(1);
    
    // Running a loop from 2 to num and
    // multiplying it with every value coming
    // in the iteration of the loop
    for(int i = 2; i <= num; i++)
    {
        obj1.Multiply(obj, i); 
    }
    
    // displaying the result
    obj1.display(obj);

}
}

输出

The factorial of the number 110 is:  
15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000

注意：除了在 display() 方法中使用尾部递归外，还可以使用循环遍历链表的节点，然后显示其数据。但是，在此之前，必须将其节点存储在堆栈中。这是因为数字阶乘的位数是以相反的顺序存储在链表中的。更新 display() 方法的以下代码，并且将得到相同的输出。

public void display1(LinkedListNode h)
{ 
    
    // creating an object of the class Stack
    // Before using the Stack class, use the appropriate import statement of it
    Stack<LinkedListNode> stk = new Stack<LinkedListNode>();
    
    while(h != null)
    {
        stk.push(h);
        h = h.next;
    }
    
    while(stk.isEmpty() == false)
    {
        LinkedListNode k = stk.pop();
        
        System.out.print(k.val);
    }
}

使用 BigInteger

还可以使用 BigInteger 类来计算大数的阶乘。在此方法中，我们将使用 BigInteger 类提供的 multiply() 方法。观察以下代码。

文件名：LargeNumFact2.java

// important import statement
import java.math.BigInteger;

public class LargeNumFact2 
{

// Returning the Factorial of num
public BigInteger factorial(int num)
{
// Initializing the result
// by instantiating the BigInteger class 
BigInteger bi = new BigInteger("1"); 

// Multiplying bi with 2, then 3, then 4, ..., then num
for (int j = 2; j <= num; j++)
{
bi = bi.multiply(BigInteger.valueOf(j));
}

return bi;
}

// main method
public static void main(String argvs[]) throws Exception
{
int num = 110;

// creating an object of the class LargeNumFact2
LargeNumFact2 obj = new LargeNumFact2();

// storing the answer 
BigInteger bi = obj.factorial(num);

System.out.println("The factorial of the number " + num + " is: " + " \n" + bi);
}
}

输出

The factorial of the number 110 is:  
15882455415227429404253703127090772871724410234473563207581748318444567162948183030959960131517678520479243672638179990208521148623422266876757623911219200000000000000000000000000

下一主题Java 中的竞争条件

Java 中大数的阶乘

示例

算法

注意：对于数字 9786，我们以相反的顺序将其数字存储在结果数组中。这是因为如果我们以数字中出现的相同顺序存储数字，那么在不使用额外空间的情况下更新 result[] 将变得困难。

实施

使用数组

使用 LinkedList

使用 BigInteger

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中大数的阶乘

示例

算法

注意：对于数字 9786，我们以相反的顺序将其数字存储在结果数组中。这是因为如果我们以数字中出现的相同顺序存储数字，那么在不使用额外空间的情况下更新 result[] 将变得困难。

实施

使用数组

使用 LinkedList

使用 BigInteger

相关帖子

Java 向后兼容性

Fascinating Number in Java

Java 中的 Boggle 搜索问题

Java 中比较两个 Excel 文件

Java 中 LongConsumer 接口及示例

java.security

Java Bellman-Ford 算法

Mirror of Matrix Across Diagonal in Java

Java 中 K 个最频繁元素

Party of Couples Problem in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器