C++ 中的格朗迪数

Grundy 数，也称为 Nim 数，对于解决 C++ 中的组合博弈论问题至关重要。它们代表游戏中位置的最小排除 (mex) 值，决定着胜负状态。通过计算 Grundy 数，玩家可以预测最优走法并分析游戏结果。

示例

输入：从 5 个物品开始。

输出

5 的 Grundy 数为：1

从 5 个物品开始是一个获胜局面。

说明

对于一个有 5 个物品的堆，其 Grundy 数为 1，表示这是一个获胜局面。这意味着玩家可以走一步，使对手处于一个失败局面（Grundy 数为 0）。通过策略性地移除 1、2 或 3 个物品，当前玩家可以控制游戏的结果。

方法 1：带记忆化的动态规划。

算法

步骤 1：定义目标：我们的目标是确定起始堆大小 n 是获胜局面还是失败局面。我们将计算从 0 到 n 的每个堆大小的 Grundy 数，其中 Grundy 数为 0 表示失败局面（无获胜走法），而任何其他数字表示获胜局面。

步骤 2：基本情况：对于一个有 0 个物品的堆，Grundy 数为 0，因为没有可用的走法了。轮到该玩家，他输了，因此这是一个失败局面。

步骤 3：每个位置的递归计算：对于任何堆大小 n：检查可能的走法：移除 1、2 或 3 个物品。对于每种走法，计算由此产生的堆大小的 Grundy 数（例如，如果我们移除 1 个物品，我们需要 n-1n-1 的 Grundy 数）。将这些产生的 Grundy 数存储在一个集合中。此步骤捕获了当前堆大小的所有可能结果。

步骤 4：计算最小排除值 (mex)：下一步是找到不在产生的 Grundy 数集合中的最小非负整数（这称为“最小排除值”或 mex）。选择 mex 值是因为它代表了当前位置无法达到的最小 Grundy 数，使其成为对手的最佳走法。

步骤 5：效率记忆化：为避免为每个堆大小重新计算 Grundy 数，请将计算出的值存储在记忆化表中（一个 数组）。如果特定堆大小的 Grundy 数已计算，我们将直接使用它，而不是重新计算。

步骤 6：最终决策：根据计算出的起始堆大小 n 的 Grundy 数：如果为 0，则这是一个失败局面（因为没有走法可以将对手置于失败局面）。如果为任何正数，则这是一个获胜局面（当前玩家有办法让对手处于失败局面）。

程序

输出

 
Grundy Number for 5 is: 1
Starting with 5 items is a winning position.   

复杂度分析

时间复杂度

由于记忆化，该算法的时间复杂度为 O(n)。每个从 0 到 n 的 Grundy 数只计算一次，因为会重用之前的结果。检查可能的走法（移除 1、2 或 3 个物品）是常数时间 O(1)，这使得该方法对于较大的 n 值都很高效。

空间复杂度

空间复杂度为 O(n)，因为我们将从 0 到 n 的每个堆大小的 Grundy 数存储在一个数组中。此记忆化表可避免重复计算。额外的空间使用非常少，因为只需要一个常数集合来跟踪每个位置可能的 Grundy 值。

方法 2：自底向上动态规划

自底向上动态规划方法是一种有效且高效的方法，可以在无需递归调用的情况下计算各种堆大小的 Grundy 数。该方法不是从目标堆大小开始并通过递归计算将其分解，而是从最小可能的堆（0 个物品）开始，然后依次构建。

程序

输出

 
Grundy Number for 5 is: 1
Starting with 5 items is a winning position.   

说明

初始化和 Grundy 数组设置

• 首先，我们定义起始堆大小 n，它表示初始堆中的物品数量（在本例中为 5）。
• 然后，我们创建一个大小为 n+1 的 vector grundy。此 vector 的每个元素将存储特定堆大小的 Grundy 数。该 vector 初始化为零，表示 grundy[0] = 0。此基本情况表示零物品的堆是一个失败局面，因为没有可用的走法。

Grundy 数的迭代计算

• 我们使用一个从 1 开始到 n 的循环。对于每个 i（代表当前堆大小），我们根据潜在的走法（移除 1、2 或 3 个物品）计算 Grundy 数。
• 为了跟踪可能的结果，我们使用一个无序集合 nextGrundy 来记录从当前堆大小 i 可达的所有位置的 Grundy 数。此集合将帮助我们确定集合 nextGrundy 中不存在的最小非负整数（这称为最小排除值，或“mex”）。

探索可能的走法

对于每个堆大小 i，玩家可以移除 1、2 或 3 个物品，只要 i 足够大即可进行该走法。

• 如果 i >= 1，我们考虑通过移除 1 个物品达到的状态，即 grundy[i - 1]。
• 如果 i >= 2，我们考虑移除 2 个物品，得到状态 grundy[i - 2]。
• 如果 i >= 3，我们考虑移除 3 个物品，得到状态 grundy[i - 3]。
• 我们将这些可达状态的 Grundy 数插入 nextGrundy 集合中，确保我们拥有从当前堆大小可能结果的集合。

计算最小排除值 (mex)

• mex，或最小排除值，是 nextGrundy 中不存在的最小非负整数。为了找到它，我们初始化 mex 为 0 并递增它，直到找到一个不存在于 nextGrundy 中的值。
• 此 mex 值成为当前堆大小 i 的 Grundy 数，表示 grundy[i] = mex。选择此值的原因是，它是从任何可能走法都无法达到的最小 Grundy 数，通过让对手远离它，为玩家提供了有利的位置。

最终决策和输出

• 在计算完所有堆大小（从 0 到 n）的 Grundy 数之后，初始堆大小 grundy[n] 的 Grundy 数告诉我们它是获胜局面还是失败局面。
• 如果 grundy[n] 为零，则起始位置是失败的，因为没有任何走法可以将对手置于失败位置。如果 grundy[n] 非零，则这是一个获胜位置，因为存在一种走法可以导致对手没有获胜选项的位置。

复杂度分析

时间复杂度

此自底向上动态规划方法的时间复杂度为 O(n)。

对 n 个值进行单次迭代

• 我们从 1 循环到 n，为每个堆大小 i 计算一次 Grundy 数。

每个堆大小的固定操作

• 对于每个堆大小 i，我们只检查三种可能的走法（移除 1、2 或 3 个物品）。每种走法都涉及恒定的工作量。
• 计算最小排除值（mex）也需要恒定的时间，因为可能的走法数量（移除 1、2 或 3 个物品）是有限的，并且不随 n 增长。

总而言之，由于我们对每个堆大小（最多为 n）执行恒定的工作量，因此总时间复杂度为 O(n)。

空间复杂度

空间复杂度为 O(n)。

Grundy 数组

• 我们创建一个大小为 n+1 的数组 grundy 来存储从 0 到 n 的每个堆大小的 Grundy 数。
• 此数组占用 O(n) 空间。

临时集合 nextGrundy

• 无序集合 nextGrundy 用于存储每个堆大小 i 的可能结果。但是，由于我们只检查三种可能的走法（移除 1、2 或 3 个物品），因此 nextGrundy 的最大长度是恒定的，即 O(1)，与 n 无关。
• 因此，nextGrundy 的空间使用量最少，并且不影响空间复杂度的缩放。

因此，总空间复杂度主要由 grundy 数组决定，结果是 O(n) 空间复杂度。