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中文网其他相关文章！