1. 概述
juggler序列以其引人入胜的行为和优雅的简单性而著称。
在这个教程中，我们将理解juggler序列，并探索如何使用给定的初始数字在Java中生成这个序列。
2. 理解juggler序列
在深入到代码生成juggler序列之前，让我们快速了解一下什么是juggler序列。
在数论中，juggler序列是一个递归定义的整数序列：
- 以一个正整数 n 作为序列的第一个项。
- 如果 n 是偶数，下一个项是 n1/2，向下取整到最接近的整数。
- 如果 n 是奇数，则下一个项是 n3/2，向下取整到最接近的整数。
这个过程会一直持续到达到1，然后序列结束。
值得注意的是，计算 n1/2 和 n3/2 都可以转化为平方根计算：
- n1/2 就是 n 的平方根，即 n1/2 = sqrt(n)
- n3/2 = n1 * n1/2 = n * sqrt(n)
一个例子可以帮助我们快速理解这个序列：
Given number: 3
-----------------
3 -> odd -> 3 * sqrt(3) -> (int)5.19.. -> 5
5 -> odd -> 5 * sqrt(5) -> (int)11.18.. -> 11
11 -> odd -> 11 * sqrt(11)-> (int)36.48.. -> 36
36 -> even -> sqrt(36) -> (int)6 -> 6
6 -> even -> sqrt(6) -> (int)2.45.. -> 2
2 -> even -> sqrt(2) -> (int)1.41.. -> 1
1
sequence: 3, 5, 11, 36, 6, 2, 1
值得注意的是，人们猜测所有的juggler序列最终都会达到1，但这个猜想尚未得到证明。因此，我们无法完成一个大O时间复杂度分析。
现在，既然我们知道如何生成juggler序列，让我们在Java中实现一些序列生成方法。
3. 循环实现的解决方案
首先，我们来实现一个基于循环的生成方法：
class JugglerSequenceGenerator {
public static List<Integer> byLoop(int n) {
if (n <= 0) {
throw new IllegalArgumentException("The initial integer must be greater than zero.");
}
List<Integer> seq = new ArrayList<>();
int current = n;
seq.add(current);
while (current != 1) {
int next = (int) (Math.sqrt(current) * (current % 2 == 0 ? 1 : current));
seq.add(next);
current = next;
}
return seq;
}
}
代码看起来相当直观。让我们快速浏览一下代码的工作原理：
- 首先，验证输入 n，因为初始数字必须是正整数。
- 然后，创建 seq 列表来存储结果序列，将初始整数赋值给 current 并添加到 seq 中。
- 一个 while 循环负责根据我们之前讨论的计算生成每个项，并将其添加到序列中。
- 当循环终止（当 current 变为1时），存储在 seq 列表中的生成序列将被返回。
接下来，我们创建一个测试方法来验证我们的循环方法是否能产生预期的结果：
assertThrows(IllegalArgumentException.class, () -> JugglerSequenceGenerator.byLoop(0));
assertEquals(List.of(3, 5, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(3));
assertEquals(List.of(4, 2, 1), JugglerSequenceGenerator.byLoop(4));
assertEquals(List.of(9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(9));
assertEquals(List.of(21, 96, 9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byLoop(21));
assertEquals(List.of(42, 6, 2, 1), JugglerSequenceGenerator.byLoop(42));
4. 递归实现的解决方案
另一种方式是使用递归从给定的数字生成juggler序列。首先，让我们在 JugglerSequenceGenerator 类中添加 byRecursion() 方法：
public static List<Integer> byRecursion(int n) {
if (n <= 0) {
throw new IllegalArgumentException("The initial integer must be greater than zero.");
}
List<Integer> seq = new ArrayList<>();
fillSeqRecursively(n, seq);
return seq;
}
如我们所见，byRecursion() 方法是另一个juggler序列生成器的入口点。它验证输入数字并准备结果序列列表。然而，主要的序列生成逻辑在 fillSeqRecursively() 方法中实现：
private static void fillSeqRecursively(int current, List<Integer> result) {
result.add(current);
if (current == 1) {
return;
}
int next = (int) (Math.sqrt(current) * (current % 2 == 0 ? 1 : current));
fillSeqRecursively(next, result);
}
代码显示，*该方法递归地调用自身，传入 next 值和 result 列表。这意味着方法会重复添加 current 数字到序列、检查终止条件以及计算下一个项的过程，直到满足终止条件（current == 1*）为止。
递归方法也通过了测试：
assertThrows(IllegalArgumentException.class, () -> JugglerSequenceGenerator.byRecursion(0));
assertEquals(List.of(3, 5, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(3));
assertEquals(List.of(4, 2, 1), JugglerSequenceGenerator.byRecursion(4));
assertEquals(List.of(9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(9));
assertEquals(List.of(21, 96, 9, 27, 140, 11, 36, 6, 2, 1), JugglerSequenceGenerator.byRecursion(21));
assertEquals(List.of(42, 6, 2, 1), JugglerSequenceGenerator.byRecursion(42));
5. 总结
在这篇文章中，我们首先讨论了juggler序列是什么。值得注意的是，所有juggler序列最终会达到1的猜想尚未得到证实。
此外，我们探讨了两种从给定整数开始生成juggler序列的方法。
如往常一样，完整示例代码可在GitHub上找到。