Java 中查找给定数字的阶乘的最后两位数

在 Java 中查找给定数字的阶乘的最后两位是一个常见的数学计算。该任务涉及计算阶乘并提取结果的最后两位数字。Java 提供了多种方法来实现这一点。

考虑一个整数 Num；任务是查找数字阶乘的最后两位。

示例 1

输入：N = 3

输出：06

示例 2

输入：N = 8

输出：40

示例 3

输入：N = 10

输出：00

方法：模算术方法

它有效地计算了阶乘模 100，确保结果中仅保留最后两位数字。该代码为确定这些最后两位数字提供了一个简单的解决方案。

算法

步骤 1：首先定义一个整数变量 num 并将其设置为所需的输入值。

步骤 2：定义一个整数变量 lastTwoDigits 来存储阶乘的最后两位数字。将其初始化为 0。

步骤 3：检查 num 的值是否大于或等于 10。如果是，则将 lastTwoDigits 设置为 0，因为大于或等于 10 的数字的阶乘在十进制表示法中将始终以“00”结尾。

步骤 4：如果 num 小于 10，则调用 findLastTwoDigitsOfFactorial 方法并将 num 作为参数传递，以计算阶乘的最后两位数字。

步骤 5：在 findLastTwoDigitsOfFactorial 方法内部

1. 初始化一个整数变量 factorial 并将其设置为 1。
2. 使用 for 循环通过从 2 迭代到 n 来计算 n 的阶乘。
3. 在每次迭代中，将 factorial 的当前值乘以 i，然后取模 100，以确保仅保留最后两位数字。
4. 返回计算出的 factorial 值，该值包含 n 的阶乘的最后两位数字。

步骤 6：打印输入 num 和输出 lastTwoDigits 以显示结果。

实施

文件名：LastTwoDigitsOfFactorial.java

输出

Input: Num = 8
Output: 20

时间复杂度：由于使用从 2 到 n 的循环计算阶乘，因此代码的时间复杂度为 O(n)。

辅助空间：辅助空间复杂度为 O(1)，因为代码使用的空间不随输入值 n 的变化而变化。

方法：使用动态规划

使用动态规划方法查找给定数字的阶乘的最后两位，涉及构建一个表或数组来有效地存储中间结果。

算法

步骤 1：首先定义一个整数变量 n 并将其设置为所需的输入值。

步骤 2：创建一个整数变量 lastTwoDigits 来存储阶乘结果的最后两位数字。

步骤 3：检查 n 是否小于或等于 1。如果为真，则返回 1，因为 0 和 1 的阶乘始终为 1，没有需要计算的附加数字。

步骤 4：创建一个大小为 n + 1 的整数数组 factorialTable 来存储阶乘值。将数组的前两个元素初始化为 1，因为 0 和 1 的阶乘是 1。

步骤 5：使用 for 循环计算并存储从 2 到 n 的阶乘值。在每次迭代中：a.将当前元素 factorialTable[i - 1] 乘以 i。b.取结果的模 100 以仅保留最后两位数字。c.将计算出的值存储在 factorialTable[i] 中。

步骤 6：循环完成后，factorialTable 数组将在 factorialTable[n] 处包含 n! 的最后两位数字。

步骤 7：返回存储在 factorialTable[n] 的值，该值代表 n 的阶乘的最后两位数字。

步骤 8：打印输入 n 和输出 lastTwoDigits 以显示结果。

实施

文件名：LastTwoDigitsOfFactorial.java

输出

Last two digits of 8! are: 20

时间复杂度：calculateLastTwoDigits 方法中的主循环从 i = 2 运行到 i <= n，迭代 n - 1 次。因此，代码的时间复杂度为 O(n)。

辅助空间：提供的代码的辅助空间复杂度为 O(n)。这主要是由于用于存储 factorialTable 数组的空间，该数组的大小为 n + 1，用于存储从 0 到 n 的数字的阶乘值。