Recaman 序列

Recaman 序列，以哥伦比亚数学家 Bernardo Recaman Santos 的名字命名，是一个引人入胜的整数序列，它吸引了数学家和计算机科学家的想象力。它由一个简单而有趣的规则定义，使其成为一个极佳的 Java 探索主题。

理解 Recaman 序列

Recaman 序列以第一个项 0 开始。有两个规则决定下一个项：

如果序列中的下一个项将是一个尚未在序列中出现的正整数，则将该整数作为下一个项。

如果下一个项是负数或已在序列中，则从当前项中减去该整数以获得下一个项。

让我们用几个初始项来说明这一点：

继续这个过程，如果正整数尚未出现在序列中，则始终选择该正整数。

Recaman 序列的前几项如下：0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, ...

规则的普遍理解

上面方法的 Java 实现描绘了使用上述递归公式计算下一个数字。

输出

时间复杂度

O(n^2)。这是因为代码可能会检查序列中每一项的所有先前项，以确保下一项是唯一的。这会导致一个嵌套循环结构，其中对于 n 个项中的每一个，在最坏情况下可能执行多达 n 次迭代。

空间复杂度

代码的空间复杂度为 O(n)，其中 n 是要生成的 Recamán 序列的项数。

上述原理的优化方法

在此方法中，我们将利用哈希技术来存储先前计算的值，从而减少重复计算值的时间。

输出

说明

在此方法中，我们定义了一个名为 generateRecamansSequence 的方法，该方法将整数 n 作为其输入参数。此 n 表示我们希望 Recamán 序列中的项数。

在深入序列生成之前，我们检查 n 是否小于或等于 0。如果 n 是无效输入（负数或零），我们将立即返回，因为没有项要生成。

接下来，我们创建一个名为 seen 的 HashSet。此 HashSet 将帮助我们跟踪序列中的唯一项。我们从一个空集开始。

我们初始化一个变量 prev 来跟踪前一项，并将其初始化为 0，因为 Recamán 序列的第一项始终是 0。

现在，我们进入一个循环，该循环从第二项 (i = 1) 迭代到第 n 项 (i < n)。在此循环中，我们一次生成一项。

在循环内部，我们根据前一项 (prev) 和 Recamán 序列的规则计算下一个项 curr。我们从 prev 中减去 i 来计算 curr。

但是，我们必须根据规则确保合同有效。如果 curr 是负数或已存在于我们的 seen HashSet 中，我们会通过添加 i 来调整它。这确保了该项是唯一的且为正数。

然后我们将 curr 添加到我们的 seen HashSet 中以跟踪它，并将其作为序列的一部分打印出来。

最后，我们将 previous 变量更新为等于 curr。这为下一次迭代做好了准备，在下一次迭代中，curr 将成为前一项。

时间复杂度：O(n)

空间复杂度：O(n)