C++ 中的 Recaman 序列

Recamán 序列是一个具有递归定义的数学序列，它提出了有趣的模式和计算挑战。每个项 j 的计算方法是：如果结果为正且尚未出现在序列中，则从 j 中减去 n，从 a0 = 0 开始。如果不是，则将 n 添加到 an−1。该序列具有振荡性和非重复性，非常适合教授 C++ 条件语句、数组和递归。该序列的视觉表示可以揭示有趣的模式。它在 C++ 中通过使用集合或哈希表有效地跟踪已使用的值和使用 vector 进行存储来实现。

什么是 Recamán 序列？

Recamán 序列的第一项始终为零。两个规则决定了下一项。

如果它尚未出现在序列中，我们应该使用一个正整数作为下一项。

Recamán 序列定义如下：

1. 序列以 a₀ =0 开始。
2. 对于 n>0
   • a_n =a_n−1 −n， 如果 a_n−1 −n 为正且尚未出现在序列中。
   • 否则，a_n= a_n−1 +n。

示例

关键方面

• 它不重复，但并非完全递增或递减。
• 它是解释编程中的递归、条件语句和序列的绝佳示例。
• 此外，它展示了一组特殊的数学运算，并在可视化时产生有趣的模式，通常表示为弧线。

算法

1. 初始化

• 首先创建一个空序列。
• 设置一个集合来记录已在序列中的数字。
• 将初始项设置为 a₀ = 0。

2. 迭代 n 项

• 从 i=1 循环到 n-1。

3. 计算下一项

• 计算 next=a_i−1+i。
  如果 next>0 且 next 不在序列中
• 将 next 添加到序列中。
  否则
• 计算 next=a_i−1+i。
• 将 next 添加到序列中。

4. 更新跟踪

• 将 next 添加到已使用数字的集合中。

5. 重复

• 这个过程一直持续到生成 n 项

6. 输出序列

• 打印或返回序列。

伪代码

上述算法的主要特点

1. 高效检查： 使用集合确保了对已使用值的常数时间查找。
2. 动态增长： 由于其增长，序列通过递归规则动态适应。
3. 输出灵活性： 序列可用于额外的分析或显示。

示例

让我们举一个例子来说明 C++ 中的Recaman 序列。

输出

Enter the number of terms in Recamán's sequence: 20
0 1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62

说明

• 输入： 用户指示要生成的项数 (n)。
• 存储： 为了防止重复，哈希集会跟踪以前使用过的数字，而向量则保存序列。
• 逻辑： 它确定从每个短语中移除 i 是否产生有效数字。如果不是，则前一个短语增加 i。
• 输出： 控制台显示序列。

结论

总之，Recamán 序列是一项创新的数学发明，它完美地捕捉了算法逻辑和递归的优雅。由于其独特的基于规则的创建，它产生了一个振荡的、非重复的序列，具有奇怪的模式，既具有视觉吸引力又具有计算上的吸引力。在 C++ 中使用 Recamán 序列是一种练习使用基本编程概念（如循环、条件语句、数组和哈希表）的有用方法。此外，该序列的迷人特性鼓励更深入的调查和深入的数学分析。通过简单的算术运算和对以前使用过的数字的有效处理，程序员可以创建和分析这个序列，展示 计算机科学和数学如何协同工作以发现迷人模式。