Generate Juggler Sequence in Java

杂耍者序列

在数论中，杂耍者序列由一个正整数 n 开始，后续的每一项都根据前一项是奇数还是偶数来确定。序列一直持续到数字 1。

如何找到杂耍者序列？

杂耍者序列递归定义如下：

1. 选择任意正整数 n 作为序列的第一个项。
2. 如果 n 是偶数，则下一项是 n^1/2，向下取整到最接近的整数。
3. 如果 n 是奇数，则下一项是 n^3/2，向下取整到最接近的整数。
4. 重复步骤 2 或 3，直到达到 1。

我们也可以简单地按照以下方式计算上述序列：

• 我们可以将 n^1/2 写成 n 的平方根。

• n^3/2 可以写成：

让我们通过一个例子来理解。

杂耍者序列示例

让我们以整数 3 作为序列的第一个项。

计算第二项

3 是奇数，因此可以使用 n¹ * n^1/2 来计算下一项。

3*√3 = 5.19 = 5

计算第三项

5 是奇数，因此可以使用 n¹ * n^1/2 来计算下一项。

5*√5 = 11.18 = 11

计算第四项

11 是奇数，因此可以使用 n¹ * n^1/2 来计算下一项。

11*√11 = 36.48 = 36

计算第五项

36 是偶数，因此可以使用 n^1/2 或 √n 来计算下一项。

√36 = 6

计算第六项

6 是偶数，因此可以使用 n^1/2 或 √n 来计算下一项。

√6 = 2.44 = 2

计算第七项

2 是偶数，因此可以使用 n^1/2 或 √n 来计算下一项。

√2 = 1.41 = 1

因此，序列是：3, 5, 11, 36, 6, 2, 1

让我们来看一些其他的杂耍者序列。

输入 10

输出 10, 3, 5, 11, 36, 6, 2, 1

输入 7

输出 7, 18, 4, 2, 1

迭代方法

迭代方法使用循环来重复执行一组指令，直到满足某个条件。它通常用于需要顺序计算或重复性任务而无需递归的问题。

算法

步骤 1：从一个正整数 n 开始，作为杂耍者序列的初始项。

步骤 2：打印 n 的值，作为序列的第一项。

步骤 3：重复以下步骤，直到 n 变为 1：

• 当 n 为偶数时，通过取 n 的平方根的下限（即 floor(sqrt(n))）来确定下一项，并将此新值赋给 n。
• 如果 n 为奇数，则通过取 n 的 1.5 次幂的下限（即 floor(n^1.5)）来找到下一项，并将 n 设置为该新结果。
• 在每次计算后打印更新后的 n 值。

步骤 4：继续重复计算并打印每一项，直到 n 变为 1。

步骤 5：一旦序列达到数字 1，就结束该过程，因为它标志着杂耍者序列的终止。

让我们在 Java 程序中实现上述步骤。

文件名：JugglerSequence.java

输出

 
Juggler Sequence for 10:
10 3 5 11 36 6 2 1   

时间复杂度：O(log N) N 在每次迭代中显著减小，因此具有对数时间复杂度。

辅助空间：O(1) 该算法使用恒定的额外空间进行计算。

使用递归

该方法使用递归通过基于当前数字是偶数还是奇数来重复应用数学运算来生成杂耍者序列。每次递归调用都会计算序列中的下一项，直到达到基本情况（n = 1）。

算法

步骤 1：从预定义的整数 n 开始，并初始化 n 以开始杂耍者序列。

步骤 2：打印 n 的当前值。显示 n 的值作为序列的一部分。

步骤 3：如果 n 为 1，则停止递归，打印它并退出递归。

步骤 4：如果 n 为偶数，则计算 floor(sqrt(n)) 并递归调用。如果 n 为偶数，则计算向下取整的 sqrt(n)，并使用新值递归调用。

步骤 5：如果 n 为奇数，则计算 floor(n^1.5) 并递归调用。如果 n 为奇数，则计算向下取整的 n^1.5，并使用新值递归调用。

让我们在 Java 程序中实现上述步骤。

文件名：JugglerSequence.java

输出

 
Juggler Sequence for 15:
15 58 7 18 4 2 1   

时间复杂度：O(log n)，这是由于每一步中 n 的递归减小。

辅助空间复杂度：O(log n)，这是由于递归堆栈。