C++ 中的斯特恩二进位序列数

在本文中，我们将讨论 C++ 中的斯特恩双原子数列及其方法、示例、时间复杂度和空间复杂度。

斯特恩双原子数列

斯特恩双原子数列是一个与 Calkin-Wilf 树密切相关的整数数列，它遵循特定的递推关系。该数列如下所示：

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …

这个数列，也被称为 fusc 函数，在组合数学和数论中有许多应用。

数论中的二叉 Calkin-Wilf 树是一种树，其中每个顶点唯一地表示一个正有理整数。树的子节点定义为 1/1+1/q=a/a+b 和 q+1=a+b/b，根节点为 1，可以是任何有理整数 q，以其最基本的分数形式 b/a 表示。

这确保了所有正有理数在树中只出现一次。开普勒的《世界的和谐》是第一批包含这一概念的作品之一，该概念以尼尔·卡尔金和赫伯特·威尔夫的名字命名。

从广度遍历这棵树会生成 Calkin-Wilf 数列。有趣的是，fusc 函数可以有效地计算斯特恩双原子数列，该数列由这次遍历中的分子（或分母，偏移一位时）的序列表示。

斯特恩双原子数列，表示为 P(n)，递归定义如下：

基本情况

P(0)=0,P(1)=1

递推关系

如果 n 是偶数

如果 n 是奇数

这个数列在数论中很重要，可以用于 Farey 数列和连分数。在斯特恩双原子数列中，前几项是 0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,…

方法

与计算斐波那契数类似，可以使用动态规划（P）来有效地解决这个问题。我们从一个 P 数组开始，其中基本情况是 P[0] = 0 和 P[1] = 1。之后，我们从 i = 2 迭代到 n，根据斯特恩双原子数列的递推关系计算每个 P[i]

如果 i 是偶数，我们使用

如果 i 是奇数，我们使用

为了实现 O(n) 的时间复杂度，我们通过存储以前计算的值来避免不必要的计算。我们的最终结果 P[n] 有效地提供了数列中所需的元素。

算法

让我们来看一个算法。

示例

让我们举一个例子来说明 C++ 中的 斯特恩双原子数列。

输出

Enter the value of n: 15
The 15th element of Stern's Diatomic Sequence is: 4   

复杂度分析

• 时间复杂度：O(N) - 算法在从 2 到 N 迭代时，利用先前存储的结果，以常数时间计算每个值，从而实现线性时间复杂度。
• 辅助空间：O(N) - 计算值存储在大小为 N+1 的 DP 数组中，占用 O(N) 的额外空间。

说明

提供的 C++ 程序使用动态规划有效地计算斯特恩双原子数列的第 n 个成员。为了避免递归方法的指数增长，它通过初始化一个向量来存储计算值，从而确保 O(n) 的时间复杂度。该数列表现出以下递推关系：对于奇数索引 S(n) = S((n-1)/2) + S((n+1)/2)，对于偶数索引 S(n) = S(n/2)。程序在验证用户输入以确保值不为负后，计算匹配的数列元素。如果输入被视为无效，则会打印错误消息并返回非零状态。在任何其他情况下，都使用结构化输出格式显示计算结果。该方法在减少冗余计算的同时，确保了高效的计算。