在 C++ 中查找斯特恩二进位序列的第 N 个元素

一组数字，称为 Stern 双原子数列，它由前两个数字之和导出。0 和 1 是起始数字，而下一个数字通过将前两个数字相加生成。例如：

0, 1, 1, 2, 3, 2, 3, 4, 5, 3, 4, 5, 6, 7,... 它有时也称为 fusc 函数。

方法

我们使用相对基本的动态规划思想来解决这个问题。通过从 q = 2 遍历到 num 并保存 series[0] = 0, series[1] = 1 的基本情况，可以轻松计算 series[i]。这是通过 Stern 双原子数列的定义完成的。之后，最后返回 series[n] 的值。它适用于各种应用和分析，因为它提供了一种生成和检索数列元素的系统方法。

查找第 n 个元素的方法

1. 初始化数列： 首先，我们初始化一个向量来存储数列的元素。向量的最初两个元素，0 和 1，被添加。
2. 生成数列： 我们使用一个循环来生成数列直到第 n 个元素。我们在循环内部添加前两个元素来计算每个后续元素。之后，这个新元素被推入向量。
3. 返回第 n 个元素： 在数列形成到那一点之后，我们从向量中返回 第 n 个 元素的值。

公式

递归关系作为 Stern 双原子数列序列 (num) 的数学定义。

对于基本情况

• 如果 num = 0，位置 num 的值为 0
• 如果 num = 1，位置 num 的值为 1

对于迭代情况

• 如果 num 是 偶数，series[num]=series[num/2]
• 如果 num 是 奇数，series[num]=series[(num-1)/2] + series[(num+1)/2]

算法

示例

让我们举一个例子来说明如何在 C++ 中从 Stern 的 双原子数列 中找到第 n 个元素。

输出

To determine the n-th Element in Stern's Diatomic Series, enter the value of num: 7
The 7-th Element in Stern's Diatomic Series is: 3

说明

在此示例中，定义了 TofindSDSFunction 函数 代码，用于通过动态规划计算 Stern 双原子数列的第 n 个元素。它初始化一个向量 series 来存储数列元素，并将 第一个元素 设置为 1。后续元素根据 q 是偶数还是奇数 迭代 计算。最终，指定函数计算第 n 个元素并在主函数中打印结果以及描述性消息，允许用户输入 num 的值。

复杂度分析

时间复杂度

• 时间复杂度为 O(n)。
• 这是因为我们遍历从 2 到 n 的范围一次，以计算数列中的每个元素。

空间复杂度

• 空间复杂度也为 O(n)。
• 我们使用一个 大小为 n+1 的向量来存储数列的元素。
• 此外，我们在主函数中为诸如 num 之类的变量使用恒定的额外空间。

时间和空间复杂度随输入值 n 线性增加。该算法效率高，可以处理较大的 n 值而无需显着开销。