C++ 中的戈隆布数列

在本文中，我们将讨论 C++ 中的 Golomb 序列及其应用和示例。

什么是 Golomb 序列？

Golomb 序列是一个非递减整数序列，其中序列中第 n 个位置的整数是整数 n 在该序列中出现的次数。Golomb 序列的某些元素是 1、2、2、3、3、4、4、4、5、5、5、6、6、6、6、7、7、7、8、8、8、8、9、9、9、10、10。正如我们从第 5 个元素中看到的，3 是 5 在序列中出现 3 次的结果。第 6 项是 4，而 6 在序列中出现了 4 次。

Golomb 序列的属性

序列的初始项是 1，第 n 项由前 n - 1 项计算得出，这些项不大于第 n 项。

示例

输入：5

输出：1 2 2 3 3

方法 1：使用递归

让我们举一个例子，使用递归在 C++ 中找到 Golomb 序列的前 n 项。

输出

1 2 2 3 3 4 4 4 5 5

说明

上述 C++ 程序计算并显示 Golomb 序列的前 'n' 个元素。Golomb 序列是一个非递减的非负整数序列，其中每个整数表示特定值在序列中出现的次数。

让我们逐步了解代码

• 在此示例中，findGolomb 函数将其参数 'n' 作为整数，并返回 Golomb 序列中第 n 个位置的元素。它基于给出斐波那契数的回溯公式。
• 当 'n' 等于 1 时，递归的终止情况达到，函数返回 1。
• 函数的递归部分通过调用 findGolomb(n) 计算 Golomb 序列的第 (n-1) 项。因此，此值被替换到计算第 n 项的公式中。
• 第 n 项是方程 1 + findGolomb(n - findGolomb(findGolomb(n - 1))) 的值。
• printGolomb 函数将整数 'n' 作为参数，并打印出 Golomb 序列的前 'n' 项。它通过对每个 i 重复调用 findGolomb 函数并打印结果来完成此操作。
• 在 main 函数中，变量 n 设置为 9，然后使用 n 作为参数调用 printGolomb 函数，以打印 Golomb 序列的前九项。

方法 2：使用动态规划

让我们举一个例子，使用动态规划在 C++ 中找到 Golomb 序列的前 n 项。

输出

1 2 2 3 3 4 4 4 5 5 

说明

以下 C++ 程序使用动态规划技术实现并显示 Golomb 序列的前 'n' 项。让我们逐步了解代码

• 在此示例中，printGolombNumbers 函数从输入中获取整数 'num' 并打印 Golomb 序列的初始 'num' 项。它利用 dp 数组来存储已计算的结果。
• Golomb 序列初始项的标识是 1，表示为 dp[1]。当 dp[1]=1 时算法开始，然后进行打印。
• 使用动态规划的算法，用于寻找 Golomb 序列的下一项。创建一个 'i' 值序列，使其从 2 开始并以 num 结束，每个项都计算为 i-th i-1 加上 num-i i-1 dp[i - 1 - dp[dp[i - 1]]]。
• dp[i] 存储在内存中并打印出来。
• 最初，通过 main 函数将变量 'num' 设置为 10，然后调用 printingGolombNumbers 函数以获取前 10 个 Golomb 数。

Golomb 序列的应用

Golomb 序列的几个应用如下：

• 随机数生成：当 C++ 涉及伪随机数生成时，可以使用 Golomb 序列。某些特定的 Golomb 值或其变体就像随机序列一样。
• 哈希函数：C++ 编程语言是我们可以用来实现“基于 Golomb 的哈希函数”的工具。这些函数可以实现以下任何一种：一种是将数据（均匀地分布在整个哈希表中）进行划分，另一种是创建布隆过滤器。可以最小化基于 Golomb 的哈希函数的冲突率；因此，它导致更高的数据检索率。
• 错误检测和纠正：Golomb 码在 C++ 编程的设计阶段对错误控制和纠正很有用。此外，通过 Golomb 算法的编码解决方案可以检测，在某些情况下还可以纠正错误，这将保持数据完整性。
• 模式识别：在 C++ 的 CNN 中使用 Golomb 数也是一种可能性，并且对模式识别非常有用。Golomb 序列适用于搜索重复模式，或用作与新序列进行比较以寻找相似模式的实验序列。

结论

总之，下面的 C++ 程序代表了两种计算和显示 Golomb 序列的前 'n' 个表示元素的方法。

第一种技术使用递归来获取序列的每个下一个元素/成员。这个 findGolomb 函数递归地返回第 n 项，以根据前一个值生成此值。之后，printGolomb 函数通过运行一个从 1 到 'n' 的循环，为每个 'i' 调用 findGolomb 来打印前 'n' 个数字。

下一个算法是动态规划技术的一个实现，用于创建 Golomb 序列。然后是 dp 数组的规范，用于存储 printGolombNumbers 函数中计算的值。算法的基本条件是 dp(1) = 1。之后，它从 2 到 num 递归地计算所有 dp(i)，通过回溯关系：dp(i) = 1 + dp(i-1 - dp(dp(i-1)))。接下来，它使用 dp[i] 作为数组，遍历每个元素并打印结果。这两种方法都会产生相同的结果，也是 Golomb 序列的前 'n' 项。