Golomb序列

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

哥倫布序列的一些項是，

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 次。

哥倫布序列的屬性 - 序列的第一項是 1，第 n 項是 1 個序列中小於或等於第 n - n 項的項數。

問題陳述

給定一個整數n。求出哥倫布序列中的前 n 項。

範例 1

Input: n = 4

Output: [1, 2, 2, 3]

範例 2

Input: n = 7

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

方法一：使用遞迴

利用哥倫布數列的性質，序列的第一項是 1。為了找到第 n 項，我們使用以下性質：第 n 項是 1 序列中小於或等於的項數到第 n - n 項。

在遞歸函數中應用此方法，如果第n 項是序列中出現時間不早於n - golomb(golomb(n - 1)) 次的最小正整數，則確保滿足該屬性，其中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 實作

在下面的程式中，我們使用遞歸來求哥倫布序列。

#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 

結論

總之，為了找出哥倫布序列，我們使用哥倫布序列的第n 個數字的屬性來找出序列中的所有數字，並使用時間複雜度從O(n^2) 到O(n) 的各種方法。

以上是Golomb序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！