C++ 中的索莫斯序列

引言

Somos 序列 在数学中是递归定义的，其与椭圆曲线、组合数学和代数几何的联系非常有趣。这个序列的奇特之处在于，尽管它是由分数定义的，但它倾向于产生整数值。

Somos 序列的一般形式由以下给出：

S_n=( s_n-1s_n-3+s_n-2s_n-2)/(s_n-4)

其中初始条件是精心选择的正整数。

理解 Somos 序列

让我们以 Somos-4 为例，这是一个众所周知的序列版本，它遵循：

S_n=( s_n-1s_n-3+s_n-2s_n-2)/(s_n-4)

初始值为

S₁=S₂=S₃=S₄=1

手动计算一些项

S₅ = (1X1+1²)/1=2

S₆ = (1X2+1²)/1= 3

S₇ = (2X3+1²)/1= 7

S₈ = (3X7+1²)/1= 23

这相当令人惊讶，因为该序列的所有项都是整数，而递归定义涉及分数。

递归方法

C++ 中的递归实现

计算 Somos 序列有一个简单的方法：递归。 让我们举一个例子来说明如何在 C++ 中使用递归方法实现 Somos 序列。

输出

递归解决方案的问题

• 时间复杂度： O(2^n)，对于大的“n”不可行。
• 冗余计算： 每次调用都会重新计算已计算过的值。

优化解决方案：记忆化

我们使用记忆化（自上而下 动态规划）来存储先前计算的值，以避免递归效率低下。让我们举一个例子来说明这种方法。

输出

记忆化的好处

• 时间复杂度从 O(2^n) 降低到 O(n)。
• 避免冗余计算： 它存储先前计算的值。

迭代动态规划方法

相反，我们可以消除这种递归并构建一个迭代变体（自下而上的动态规划方法），它在时间和空间复杂度上都更高效。让我们举一个例子来说明这种方法。

输出

迭代方法的优点

• 时间复杂度： O(n)。
• 空间复杂度： O(n)。
• 它避免了递归函数调用的开销。

进一步优化：节省空间的方法

我们只需要最后四个计算值，这使我们能够使用滚动 数组 方法将空间减少到 O(1)。让我们举一个例子来说明这种方法。

输出

最终复杂度分析

结论

总之，Somos 序列 是数学中一个奇怪的构造，它以分数定义但仍保持整数值。我们考虑了几种在 C++ 中计算它的方法。一种是朴素的递归方法，另一种是空间复杂度为 O(1) 的优化迭代版本。这最后一个版本是实际使用的最佳实现。