C++ 中的乌拉姆数序列

在本文中，我们将讨论 C++ 中的乌拉姆数列及其工作原理、伪代码和示例。

什么是 C++ 中的乌拉姆数列？

1964 年，斯坦尼斯瓦夫·乌拉姆设计了一个数列，今天被称为乌拉姆数。这个数学数列的最初两个正整数用 U1 和 U2 表示。下一个数字是前两个不同项之和，依此类推。这些是和只能以一种方式表示的最小整数。这个系列有助于说明唯一加法和唯一性要求之间的相互作用。构建这样一个序列的方法是在 C++ 中使用哈希映射跟踪和，以及另一个类似的数据结构并保留一个单词列表。它确保计算正确完成，必须遵循序列的规则，这也使得它在娱乐数学和算法设计中非常常见。

以下是乌拉姆序列的工作步骤

• 初始化：从初始词 U₁ 和 U₂ 开始。例如，假设 U₁=1 和 U₂=2。
• 序列的创建：为了计算后续项，确定大于最终项的最小整数，该整数只能以一种方式写成前两个不同项之和。
• 唯一性条件：如果一个数字可以用多种方式表示为以前项之和，则该数字不包含在序列中。

例如，从 U₁ =1 和 U₂ =2 开始。

下一个项是 U₃ =3，因为 3=1+2。

下一个项是 U₄ =4，因为 4=1+3。

序列继续为 1,2,3,4,6,8,……

伪代码

初始化变量

• 首先，创建一个列表 ulamSequence 并插入 u₁, u₂。
• 创建一个有序集合 candidates 来存储潜在的下一个乌拉姆数。
• 创建一个哈希映射 sumCounts 来跟踪和的出现次数。

设置初始值

• 计算 u₁+ u₂
• 将 u1+u2 添加到 candidates 并设置 sumCounts[u1 + u2] = 1。

生成乌拉姆数

• 当 ulamSequence 的大小小于 n 时
• 从 candidates 中提取最小的数字作为 nextUlam。
• 将 nextUlam 添加到 ulamSequence 的末尾。
• 从 candidates 中移除 nextUlam。

对于 ulamSequence 中每个小于 nextUlam 的数字 num

• 计算 newSum=num+nextUlam。
• 将 sumCounts[newSum] 增加 1。
• 如果 sumCounts[newSum] == 1
• 将 newSum 添加到 candidates。
• 否则，如果 sumCounts[newSum] > 1
• 从 candidates 中移除 newSum（因为它违反了唯一性）。
• 返回结果
• 返回 ulamSequence。

C++ 实现

在 C++ 中创建乌拉姆数通常需要

• 定义前两个项。
• 重复计算后续项，同时跟踪前一个项的和。
• 计算和的出现次数以满足唯一性要求。

示例 1

输出

Ulam Sequence: 1 2 3 4 6 8 11 13 16 18   

说明

• 向量 ulamSequence 包含前两个项 u₁ 和 u₂ 的初始化。
• 唯一性检查：使用无序映射 sumCounts 跟踪和及其出现次数。
• 序列生成：该软件对每个新单词的潜在可能性进行迭代，将以前的项相加，以确保满足唯一性条件。

示例 2：使用 std::set 和 std::unordered_map

输出

Ulam Sequence: 1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69   

结论

总之，乌拉姆数列中的每个数字都必须以唯一的方式表示为两个不同的前一个数字之和，这使其成为对数学极限和原理的有趣研究。它的算法生成说明了数据结构和计算逻辑如何很好地协同工作。哈希映射和有序集等方法保证了速度和正确性。这恰好是编程中如何在 C++ 中保持计算效率同时包含特殊情况的一个很好的例子。除了其理论吸引力之外，研究和创建乌拉姆序列还可以提高解决问题的能力，同时展示算法思维的美妙。