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