在 Java 中產生 Juggler 序列

1. 概述

雜耍者的鏡頭以其有趣的行為和優雅的簡潔而引人注目。

在本教程中，我們將了解雜耍者序列並探索如何使用 Java 中給定的初始數字生成序列。

2. 理解雜耍者序列

在我們深入研究產生雜耍序列的程式碼之前，讓我們先快速了解雜耍序列是什麼。

在數論中，雜耍者序列是遞歸定義的整數序列，如下所示：

從正整數n作為序列的第一項開始。
若n為偶數，則下一項為n 1/2 ，向下捨去至最接近的整數。
若n為奇數，則下一項為n 3/2 ，向下捨去至最接近的整數。

此過程將持續直至達到 1，序列在此終止。

值得一提的是， n 1/2和n 3/2都可以轉換成平方根計算：

n 1/2是n.因此n 1/2 = sqrt(n)
n 3/2 = n 1 * n 1/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

值得注意的是，據推測所有雜耍者序列最終都會達到1，但這個猜想尚未得到證明。因此，我們實際上無法完成 Big O 時間複雜度分析。

現在我們知道了雜耍者序列是如何產生的，讓我們用 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. 基於遞歸的解決方案

或者，我們可以從給定的數字遞歸地產生一個雜耍序列。首先，我們將byRecursion()方法加入JugglerSequenceGenerator類別：

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()方法是另一個雜耍序列產生器的入口點。它驗證輸入數字並準備結果序列清單。然而，主要的序列生成邏輯是在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. 結論

在本文中，我們首先討論了什麼是雜耍序列。值得注意的是，目前尚未證明所有雜耍序列最終都會達到 1。

此外，我們還探索了兩種從給定整數開始產生雜耍序列的方法。

與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。

本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議