哥伦布序列 - 哥伦布序列是一个非递减的整数序列,其中第 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
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 golombSeq(int n){
vector seq(n, 0);
for (int i = 1; i