本文探讨了如何在给定范围内查找阶乘首位为偶数的数字。针对传统数据类型在计算大数阶乘时可能遇到的溢出问题，文章详细介绍了如何利用java的`biginteger`处理任意大小的阶乘结果，并结合备忘录模式（memoization）优化计算过程，避免重复计算，从而实现高效且准确的解决方案。
问题描述
我们的目标是在一个指定的整数范围 [a, b] 内，找出所有满足其阶乘结果的首位数字为偶数的整数。例如，在 [1, 10] 的范围内，2! = 2 (首位为偶数), 3! = 6 (首位为偶数), 4! = 24 (首位为偶数), 8! = 40320 (首位为偶数)。因此，该范围内的结果应为 [2, 3, 4, 8]。
常见陷阱：long 类型溢出
在处理阶乘计算时，一个常见的陷阱是使用标准整数类型（如 int 或 long）来存储结果。阶乘函数增长非常迅速：
- 13! = 6,227,020,800
- 20! = 2,432,902,008,176,640,000 Java的 long 类型最大值约为 9 * 10^18。这意味着，当计算 20! 时，long 类型就会发生溢出，导致结果不正确。
考虑以下原始代码片段：
Listprocess(int a, int b) { long base = i; // 这里的i应该初始化为1，并计算a! for(int i=1; i<=a; i++) base *= i; // 假设这里是计算a! if(even(base)) list.add(a); // 这里的even(base)在溢出后会给出错误结果 for(int i=a+1; i<=b; i++) { base *= i; // 从a+1开始，base继续乘以i if(even(base)) list.add(i); } return list; } boolean even(long k) { // 将long转换为字符串，然后检查首位 int z = ("" + k).charAt(0) - '0'; return z % 2 == 0; }
这段代码在 a 或 b 较大时会失败，因为 long 类型的 base 会在 20! 左右溢出。一旦溢出，base 的值将不再代表真实的阶乘结果，后续通过 ("" + k).charAt(0) 获取的首位数字也将是错误的。这就是为什么在编码挑战中会有隐藏测试用例失败的原因。
解决方案核心：BigInteger 的应用
为了解决 long 类型溢出的问题，我们需要使用能够处理任意精度整数的类型。在 Java 中，java.math.BigInteger 类正是为此目的设计的。BigInteger 对象可以存储任意大小的整数，从而确保阶乘计算的准确性，无论数字有多大。
使用 BigInteger 进行阶乘计算的基本思路是：
- 初始化一个 BigInteger 对象为 1。
- 在循环中，将当前的 BigInteger 结果与下一个整数（作为 BigInteger 对象）相乘。
性能优化：备忘录模式（Memoization）
在给定范围 [a, b] 内查找数字时，我们可能需要计算多个连续的阶乘（例如 5!、6!、7! 等）。每次都从头开始计算阶乘效率较低。备忘录模式（或动态规划的自底向上方法）可以显著提高效率。
其思想是：
- 存储已经计算过的阶乘结果及其首位数字的奇偶性。
- 当需要计算 n! 时，首先检查是否已经计算过。
- 如果已经计算过，直接返回存储的结果。
- 如果未计算过，则从上一个已计算的阶乘 (n-1)! 开始，逐步计算到 n!，并将每个中间结果及其首位数字的奇偶性存储起来，以供将来使用。
实现细节与代码示例
我们将创建一个 Fact 记录（或一个简单的类）来存储每个数字 n 对应的 BigInteger 阶乘值和其首位数字的奇偶性。
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class FactorialFirstDigitParity {
// Fact 记录用于存储阶乘结果、对应的数字n以及首位数字的奇偶性
// parity为true表示首位为偶数，false表示首位为奇数
record Fact(BigInteger fact, int n, boolean parity) {}
// 静态列表用于存储已计算的阶乘结果，实现备忘录模式
// 初始化时包含0!, 1!, 2! 的结果
static List computed = new ArrayList<>(List.of(
new Fact(BigInteger.ONE, 0, false), // 0! = 1 (首位为奇数)
new Fact(BigInteger.ONE, 1, false), // 1! = 1 (首位为奇数)
new Fact(BigInteger.TWO, 2, true) // 2! = 2 (首位为偶数)
));
/**
* 判断给定数字 n 的阶乘首位是否为偶数。
* 使用备忘录模式优化。
* @param n 要计算阶乘的数字
* @return 如果 n! 的首位为偶数，则返回 true；否则返回 false。
*/
public static boolean factorialStartsWithEven(int n) {
// 如果 n 小于等于当前已计算的最大阶乘数，直接从备忘录中获取结果
if (n < computed.size()) {
return computed.get(n).parity;
}
// 获取备忘录中最后一个已计算的阶乘结果
Fact lastComputedFact = computed.get(computed.size() - 1);
BigInteger currentFactValue = lastComputedFact.fact; // 从上一个阶乘值开始
Fact result = null;
// 从上一个已计算的数字 n+1 开始，逐步计算到目标 n
for (int k = lastComputedFact.n + 1; k <= n; k++) {
// 计算新的阶乘值： (k-1)! * k
currentFactValue = currentFactValue.multiply(BigInteger.valueOf(k));
// 获取当前阶乘值的字符串表示，并提取首位数字
char firstChar = currentFactValue.toString().charAt(0);
int firstDigit = Character.digit(firstChar, 10); // 将字符转换为数字
// 判断首位数字的奇偶性
boolean isEvenParity = (firstDigit % 2 == 0);
// 创建新的 Fact 记录并添加到备忘录中
result = new Fact(currentFactValue, k, isEvenParity);
computed.add(result);
}
// 返回目标 n 的阶乘首位奇偶性
return result.parity;
}
/**
* 在指定范围内查找所有阶乘首位为偶数的数字。
* @param start 范围的起始值
* @param end 范围的结束值
* @return 包含所有符合条件的数字的列表
*/
public static List getForRange(int start, int end) {
List results = new ArrayList<>();
for (int i = start; i <= end; i++) {
if (factorialStartsWithEven(i)) {
results.add(i);
}
}
return results;
}
public static void main(String[] args) {
// 示例用法：查找 1 到 20 之间阶乘首位为偶数的数字
List list = getForRange(1, 20);
System.out.println("在 [1, 20] 范围内，阶乘首位为偶数的数字有: " + list);
// 预期输出: [2, 3, 4, 8, 12, 13, 14, 16, 18, 20]
// 示例用法：查找 1 到 10 之间阶乘首位为偶数的数字
List listSmallRange = getForRange(1, 10);
System.out.println("在 [1, 10] 范围内，阶乘首位为偶数的数字有: " + listSmallRange);
// 预期输出: [2, 3, 4, 8]
}
} 代码说明：
- Fact 记录： 一个简洁的数据结构，用于封装阶乘值 (BigInteger fact)、对应的数字 (int n) 和其首位数字的奇偶性 (boolean parity)。
- computed 列表： 这是一个静态的 ArrayList，作为我们的备忘录。它预先存储了 0!、1! 和 2! 的结果，以便后续计算可以从已知点开始。
-
factorialStartsWithEven(int n) 方法：
- 首先检查 n 是否已经在 computed 列表中。如果是，直接返回已存储的奇偶性，这是备忘录模式的关键。
- 如果 n 尚未计算，它会从 computed 列表中最后一个已知的阶乘值 (lastComputedFact) 开始，逐步计算到 n!。
- 在每次迭代中，currentFactValue 会乘以 k，得到新的阶乘值。
- currentFactValue.toString().charAt(0) 用于获取 BigInteger 结果的首位字符。
- Character.digit(firstChar, 10) 将字符转换为对应的整数数字。
- firstDigit % 2 == 0 判断首位数字的奇偶性。
- 每个计算出的阶乘结果（Fact 对象）都会被添加到 computed 列表中，以便后续查询。
- getForRange(int start, int end) 方法： 遍历指定范围 [start, end] 中的每个数字，调用 factorialStartsWithEven 方法，并将所有符合条件的数字收集到一个列表中返回。
- main 方法： 提供了示例用法，展示了如何调用 getForRange 方法并打印结果。
总结与注意事项
- 大数处理： 当计算结果可能超出 long 类型的最大值时，务必使用 BigInteger。这是解决阶乘首位数字判断问题的根本。
- 性能优化： 备忘录模式（Memoization）对于涉及重复子问题计算的场景非常有效。在本例中，它避免了每次都从 1! 开始计算阶乘，显著提升了处理较大范围或多次查询时的效率。
- 首位数字提取： BigInteger 对象可以直接转换为字符串，然后通过 charAt(0) 提取首位字符，再转换为数字进行奇偶性判断。
- 代码可读性： 使用 record（Java 16+）可以简洁地定义数据载体，提高代码的可读性。如果使用旧版本 Java，可以使用一个普通的类来实现 Fact 的功能。
通过上述方法，我们可以健壮且高效地解决在给定范围内查找阶乘首位数字为偶数的问题，即使涉及大数阶乘计算也能保证准确性。
