哥伦布序列 - 哥伦布序列是一个非递减的整数序列，其中第 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) 的各种方法。
