Golomb 序列

---

Golomb 序列 - Golomb 序列是一個非遞減的整數序列，其中第 n 項的值是整數 n 在序列中出現的次數。

Golomb 序列的一些項為：

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, …

在這裡，我們可以看到，第 5 項是 3，並且 5 在序列中也出現了 3 次。

第 6 項是 4，並且 6 在序列中也出現了 4 次。

Golomb 序列的性質 - 序列的第一項是 1，第 n 項是 1 加上序列中小於或等於 n - 第 n 項的項數。

問題陳述

給定一個整數 n。找到 Golomb 序列中的前 n 項。

示例 1

Input: n = 4

Output: [1, 2, 2, 3]

示例 2

Input: n = 7

Output: [1, 2, 2, 3, 3, 4, 4]

方法 1：使用遞迴

根據 Golomb 序列的性質，序列的第一項是 1。為了找到第 n 項，我們使用以下性質：第 n 項是 1 加上序列中小於或等於 n - 第 n 項的項數。

在遞迴函式中應用此方法，我們確保如果第 n 項是最小的正整數，並且該整數在序列中出現的次數不超過 n - golomb(golomb(n - 1)) 次，則該性質得到滿足，其中 golomb() 是用於查詢 Golomb 序列第 n 項的遞迴函式。

虛擬碼

procedure golomb (n)
   if n == 1
      ans = 1
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1)))
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   for i = 1 to n
      seq[i - 1] = golomb(i)
   ans = seq
end procedure

示例：C++ 實現

在以下程式中，我們使用遞迴來查詢 Golomb 序列。

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n){

   // First element is 1
   if (n == 1) {
      return 1;
   }
   
   // Satisfying property of golomb sequence for the nth number
   return 1 + golomb(n - golomb(golomb(n - 1)));
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i);    
      }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++)    {
      cout << seq[i] << " ";
   }
   return 0;
} 

輸出

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

時間複雜度 - O(n^2)，因為每個項都是透過遞迴計算前一項來計算的。

空間複雜度 - O(n)

方法 2：帶備忘錄的遞迴

為了記憶遞迴程式碼，我們建立一個對映來儲存先前計算的值，這些值是在上述程式碼中遞迴計算的。然後，在計算每個數字時，首先檢查先前的數字是否已計算，如果已計算，則採用先前計算的結果，否則計算它。

虛擬碼

golomb (n, t)
   if n == 1
      ans = 1
   end if
   if n is present in t
      ans = t[n]
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1, t), t), t)
   t[n] = ans
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   Initialize map: t
   for i = 1 to n
       seq[i - 1] = golomb(i, t)
   ans = seq
end procedure

示例：C++ 實現

在以下程式中，先前的計算結果儲存在一個對映中，並在計算一項時訪問該對映。

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n, map<int, int> &t){

   // First term is 1
   if (n == 1){
      return 1;
   }
   
   // Checking if the term is previously computed
   if (t.find(n) != t.end()){
      return t[n];
   }
   int result = 1 + golomb(n - golomb(golomb(n - 1, t), t), t);
   
   // Saving the term to map
   t[n] = result;
   return result;
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   map<int, int> t;
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i, t);
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

輸出

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

時間複雜度 - O(nlogn)

空間複雜度 - O(n)

方法 3：動態規劃

使用動態規劃，我們建立一個大小為 n+1 * 1 的 dp 表。然後使用上面使用的性質（其中第 n 個數字是 1 + golomb(n - golomb(golomb(n - 1)))），計算序列中的所有數字並將它們儲存在向量中。

虛擬碼

procedure golombSeq (n)
   seq[n] = {0}
   seq[0] = 1
      Initialize the dp table of size n+1, 1
   for i = 2 to n
      dp[i] = dp[i - dp[dp[i - 1]]] + 1
   for i = 1 to n
      seq[i-1] = dp[i]
   ans = seq
end procedure

示例：C++ 實現

在以下程式中，我們使用動態規劃方法來解決問題。

#include <bits/stdc++.h>
using namespace std;
// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   
   // First term is 1
   seq[0] = 1;
   vector<int> dp(n + 1, 1);
   for (int i = 2; i <= n; i++){
   
      // Satisfying the property that nth term is 1 + golomb(n - golomb(golomb(n - 1)))
      dp[i] = dp[i - dp[dp[i - 1]]] + 1;
   }
   for (int i = 1; i <= n; i++){
      seq[i - 1] = dp[i];
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

輸出

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 

結論

總之，為了找到 Golomb 序列，我們使用 Golomb 序列第 n 個數字的性質，使用各種方法找到序列中的所有數字，這些方法的時間複雜度從 O(n^2) 到 O(n)。