用 Java 計算 Padovan 序列
1. 概述
帕多萬數列是一種類似斐波那契數列的模式，其中前兩項和前三項決定了每一項。它由理查德·帕多萬在20世紀90年代提出（此前也有其他人研究過），應用於建築學、自然生長模式和組合數學等領域，尤其適用於計算某些鋪磚圖案和幾何圖形。它之所以流行，是因為它像斐波那契數列一樣，將簡單的規則與令人驚嘆的結構聯繫起來。
因此，由於它與斐波那契數列相似，我們可以使用相同的方法來找到它，因此，我們也需要避免相同的陷阱。在本教程中，我們將探討產生此數列的幾種可能方法及其優缺點。雖然可以使用 Stream API 或建立生成器來延遲產生值，但考慮到實作的複雜性和程式碼可讀性，我們暫不考慮這些方法。
2. 帕多瓦序列
帕多瓦數 P(n) 由以下遞推關係定義：
P(n) = P(n-2) + P(n-3), with P(0) = P(1) = P(2) = 1.因此，我們可以用這個公式來產生前幾項：1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, …
帕多萬數出現在組合數學（例如，計算某些鋪磚和單字）、幾何、建築和成長模型。我們可以看到，它與斐波那契數列非常相似，斐波那契數列使用F(n) = F(n-1) + F(n-2) ；而帕多萬數使用P(n) = P(n-2) + P(n-3) ，這使得它的增長速度較慢。
3. 遞迴方法
最簡單的選擇是遞歸方法；雖然不太實用，但由於這是人們熟悉遞歸的常用方法，所以這可能是個不錯的入門方法：
public static int nthPadovanTermRecursiveMethod(int n) {
if (n == 0 || n == 1 || n == 2) {
return 1;
}
return nthPadovanTermRecursiveMethod(n - 2) + nthPadovanTermRecursiveMethod(n - 3);
}然而，需要注意的是，我們應該僅將此方案用於教學目的。此方案效率極低，時間複雜度為O(2^n) ，空間複雜度為線性（用於維護呼叫堆疊）。我們可以透過引入記憶化來降低時間複雜度，使其降至O(n):
public static int nthPadovanTermRecursiveMethodWithMemoization(int n) {
if (n == 0 || n == 1 || n == 2) {
return 1;
}
int[] memo = new int[n + 1];
memo[0] = 1;
memo[1] = 1;
memo[2] = 1;
return nthPadovanTermRecursiveMethodWithMemoization(n, memo);
}
private static int nthPadovanTermRecursiveMethodWithMemoization(int n, int[] memo) {
if (memo[n] != 0) {
return memo[n];
}
memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2, memo)
+ nthPadovanTermRecursiveMethodWithMemoization(n - 3, memo);
return memo[n];
}雖然我們取得了一些進展，但解決方案速度仍然很慢，而且佔用了不必要的空間。
4. 迭代方法
然而，使用遞歸來解決這類問題只是權宜之計，不應該在生產環境或任何對效能有要求的程式碼中使用。因此，我們可以嘗試使用迭代解決方案來解決這個問題：
public static int nthPadovanTermIterativeMethodWithArray(int n) {
int[] memo = new int[n + 1];
if (n == 0 || n == 1 || n == 2) {
return 1;
}
memo[0] = 1;
memo[1] = 1;
memo[2] = 1;
for (int i = 3; i <= n; i++) {
memo[i] = memo[i - 2] + memo[i - 3];
}
return memo[n];
}在這種情況下，我們沿用相同的思路，但不用遞歸調用，而是使用數組來保存先前的值。雖然這種方法在複雜度上沒有比之前的方法有所改進（時間和空間複雜度仍然是線性的），但我們可以將其作為進一步改進的墊腳石。很容易看出，我們只需要三個數字：
public static int nthPadovanTermIterativeMethodWithVariables(int n) {
if (n == 0 || n == 1 || n == 2) {
return 1;
}
int p0 = 1, p1 = 1, p2 = 1;
int tempNthTerm;
for (int i = 3; i <= n; i++) {
tempNthTerm = p0 + p1;
p0 = p1;
p1 = p2;
p2 = tempNthTerm;
}
return p2;
}
這是一個相當不錯的改進：我們仍然保持線性時間複雜度，但空間複雜度降低到了一個常數。
5. 比奈公式
然而，我們可以進一步簡化計算，使用一個簡單的公式。由於這些數字的比值是恆定的，所以我們完全不需要進行任何複雜的運算：
public static int nthPadovanTermUsingFormula(int n) {
if (n == 0 || n == 1 || n == 2) {
return 1;
}
// Padovan spiral constant (plastic number) - the real root of x^3 - x - 1 = 0
final double PADOVAN_CONSTANT = 1.32471795724474602596;
// Normalization factor to approximate Padovan sequence values
final double NORMALIZATION_FACTOR = 1.045356793252532962;
double p = Math.pow(PADOVAN_CONSTANT, n - 1);
return (int) Math.round(p / NORMALIZATION_FACTOR);
}這種方法可以在常數時間內計算出任意n-th個數；但是，它使用的是近似值。因此，必須考慮所有可能出現的問題，並使用更多的小數位數，例如使用BigDecimal 。
6. 結論
至於斐波那契數列，我們可以用多種不同的方法來計算帕多瓦數列。每種方法都有其自身的優點和缺點（即使僅從簡易性和教學意義而言）。因此，我們可以根據具體需求選擇最適合的方法。像往常一樣，本教程的所有程式碼都可以在 GitHub 上找到。