下一篇 → ← 上一篇

Java 中的阶乘程序

2025年7月28日 | 阅读 6 分钟

非负整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。阶乘通常用于组合和排列（数学）。n 的阶乘表示为 n!。

计算数字 n 的阶乘的公式是

边缘情况

0!=1

负整数的阶乘是未定义的

示例

4! = 4*3*2*1 = 24
5! = 5*4*3*2*1 = 120

这里，4! 发音为“4 factorial”。它也称为“4 bang”或“4 shriek”。

Java 中的阶乘程序

在 Java 中编写阶乘程序有许多方法。

使用 for 循环
使用 while 循环
使用 do-while 循环
使用递归
使用动态规划

使用 for 循环

让我们看看 Java 中使用循环的阶乘程序。

示例

class Main {
	public static void main(String args[]) {
		int i, fact = 1;
		int number = 5;// It is the number to calculate the factorial
		for (i = 1; i <= number; i++) {
			fact = fact * i;
		}
		System.out.println("Factorial of " + number + " is: " + fact);
	}
}

编译并运行

输出

Factorial of 5 is: 120

时间复杂度：O(n)

迭代方法实现一个从 1 开始到 n 结束的单个循环。每次迭代都需要恒定的时间（进行乘法运算）。

空间复杂度：O(1)

迭代方法仅分配固定的额外空间，与输入大小无关。它不依赖于系列中的最后一个数字 (n)。

使用 while 循环

示例

public class Main {
	public static void main(String[] args) {
		int n = 6; // Change this to any positive integer
		int result = 1;
		int i = 1;
		while (i <= n) {
			result *= i;
			i++;
		}
		System.out.println("Factorial of " + n + " is: " + result);
	}
}

编译并运行

输出

Factorial of 6 is: 720

时间复杂度： while 循环从 1 迭代到 n，每次迭代执行一次乘法。因此，对于输入 n，循环运行 n 次。所以，时间复杂度是 O(n)。

空间复杂度： 不使用递归或动态内存分配，因此空间复杂度为 O(1)。

使用 do-while 循环

示例

public class Main {
	public static void main(String[] args) {
		int n = 3; // Change this to any positive integer
		int result = 1;
		int i = 1;
		do {
			result *= i;
			i++;
		} while (i <= n);
		System.out.println("Factorial of " + n + " is: " + result);
	}
}

编译并运行

输出

Factorial of 3 is: 6

时间复杂度： while 循环从 1 迭代到 n，每次迭代执行一次乘法。因此，对于输入 n，循环运行 n 次。所以，时间复杂度是 O(n)。

空间复杂度： 不使用递归或动态内存分配，因此空间复杂度为 O(1)。

使用递归

让我们看看使用递归的 Java 阶乘程序。

示例

class Main {
	static int factorial(int n) {
		if (n == 0)
			return 1;
		else
			return (n * factorial(n - 1));
	}
	public static void main(String args[]) {
		int fact = 1;
		int number = 4;// It is the number to calculate the factorial
		fact = factorial(number);
		System.out.println("Factorial of " + number + " is: " + fact);
	}
}

编译并运行

输出

Factorial of 4 is: 24

时间复杂度：O(n)

这个程序的时间复杂度也是 O(n)，最坏情况涉及 n 次递归调用，每次调用耗时恒定。

空间复杂度：O(n)

递归操作的空间复杂度为 O(n)，因为每次函数调用都会为调用栈分配内存。在最坏的情况下，递归树的大小是 n，这意味着调用栈使用 O(n) 的空间。

使用动态规划

1. 制表（自底向上）方法

制表方法涉及迭代地填充表（通常是数组）来存储子问题的结果，从最小的子问题开始，逐渐构建到最终解决方案。

让我们看看使用制表的 Java 阶乘程序。

示例

public class Main {
	public static int factorial(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("Factorial is not defined for negative numbers");
		}
		int[] dp = new int[n + 1];
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			dp[i] = dp[i - 1] * i;
		}
		return dp[n];
	}
	public static void main(String[] args) {
		int number = 7; // Example number
		System.out.println("Factorial of " + number + " is: " + factorial(number));
	}
}

编译并运行

输出

Factorial of 7 is: 5040

时间复杂度：O(n)

制表方法只循环一次 1 到 n 的数字来计算它们的阶乘。因此，时间复杂度是 O(n)，这与输入大小 (n) 呈线性关系。

空间复杂度：O(n)

空间复杂度也为 O(n)，因为数组的大小是 n+1，用于存储阶乘值。

记忆化（自顶向下 DP）方法

记忆化方法涉及存储已计算过的子问题的结果，以避免在递归过程中进行重复计算。

让我们看看使用记忆化的 Java 阶乘程序。

示例

import java.util.HashMap;
import java.util.Map;
public class Main {
	private static Map<Integer, Integer> memo = new HashMap<>();
	public static int factorial(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("Factorial is not defined for negative numbers");
		}
		if (n == 0 || n == 1) {
			return 1;
		}
		if (memo.containsKey(n)) {
			return memo.get(n);
		}
		int result = n * factorial(n - 1);
		memo.put(n, result);
		return result;
	}
	public static void main(String[] args) {
		int number = 8; // Example number
		System.out.println("Factorial of " + number + " is: " + factorial(number));
	}
}

编译并运行

输出

Factorial of 8 is: 40320

时间复杂度：O(n)

然而，尽管看起来 O(n^2) 的时间复杂度来自递归调用，但记忆化确保每个值只计算一次。换句话说，算法的复杂度是线性的。

空间复杂度：O(n)

时间复杂度为 O(n)，因为这是一个使用调用栈的递归算法。更重要的是，记忆化缓存（HashMap）的值在空间复杂度上为 O(n)，因为可以存储 n 个每个大小恒定的条目。

Java 阶乘程序选择题

1. 在 Java 中计算大数阶乘时，使用 BigInteger 而不是 int 或 long 的主要优势是什么？

BigInteger 比 int 和 long 更快。
BigInteger 提供内置的阶乘方法。
BigInteger 可以处理任意大的数字而不会溢出。
BigInteger 比 int 和 long 使用的内存更少。

答案：c)

解释： BigInteger 可以处理任意大的数字而不会溢出，这在计算大数阶乘时是一个显著的优势，否则这些大数会超出 int 或 long 的存储容量。

2. 考虑到计算效率，在 Java 中计算阶乘哪种方法通常更节省内存？

迭代方法
递归方法
使用 BigInteger
使用记忆化

答案：a)

解释： 迭代方法通常比递归方法更节省内存，因为它不涉及多次函数调用及其相关的调用栈使用开销。

3. 在 Java 中计算大数阶乘时，以下哪项可能导致堆栈溢出错误？

使用迭代方法
使用递归方法
使用 BigInteger
使用 for 循环

答案：b)

解释： 当使用递归方法计算大数阶乘时，可能会发生堆栈溢出错误，因为每次递归调用都会消耗堆栈空间，大量的调用可能会超出堆栈的限制。

4. 在 Java 中计算数字的阶乘的迭代和递归方法的复杂度是多少？

O(1)
O(log n)
O(n)
O(n^2)

答案：c)

解释： 计算数字的阶乘的迭代和递归方法的时间复杂度都为 O(n)，因为它们都涉及一个循环或一系列递归调用，这些调用会迭代或递归 n 次。

5. 使用递归计算数字的阶乘时，如何优化性能并避免重复计算？

通过使用更大的堆栈大小
通过使用记忆化
通过增加 JVM 堆大小
通过使用多线程

答案：b)

解释： 记忆化是一种通过存储昂贵函数调用的结果并在出现相同输入时重用它们来优化递归函数性能的技术，从而避免重复计算。

下一个主题Java 程序

← 上一篇下一篇 →

相关帖子

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

关注我们

教程

Java 数据结构 C 语言 C++ 教程 C# 教程 PHP 教程 HTML 教程 JavaScript 教程 jQuery 教程 Spring 教程

面试题

Microsoft Amazon Adobe Intuit Accenture Cognizant Capgemini Wipro Tcs Infosys

在线编译器

C R C++ Php Java Html Swift Python JavaScript TypeScript

最新帖子 | 教程列表 | 隐私政策 | 关于我们 | 联系我们

© 版权所有 2011 - 2025 TpointTech.com。保留所有权利。