Golomb序列

2023年 8月 27日 52.2k 0

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

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论