algorithm - 零和一个的游戏(谷歌采访)

Question

不久前我在谷歌面试时被问到这个问题，到目前为止我还没有找到一个好的答案: 这是一款 2 人游戏，您将获得一串零和一。在每个回合中，玩家可以选择一个 1(或彼此相邻的多个 1)并将其/它们更改为 0/0。将最后的 1(或一组 1)更改为 0/0 的玩家是游戏的赢家。

例如从 0101110 开始。第一个玩家有 7 种可能的移动:

1. 0101110 -> 0001110(第二个玩家可以赢)
2. 0101110 -> 0100110(第二个玩家可以赢)
3. 0101110 -> 0101010(第二个玩家可以赢)
4. 0101110 -> 0101100(第二个玩家可以赢)
5. 0101110 -> 0100010(先手赢)
6. 0101110 -> 0101000(先手赢)
7. 0101110 -> 0100000(第二个玩家可以赢)

目标是找出如果您先开始是否有获胜策略。 我们在这里假设两个玩家都是好玩家(意味着他们不会犯错误!)

更新: 这个游戏与 Nim ( https://en.wikipedia.org/wiki/Nim ) 略有不同，对于 Nim 来说，堆(或堆)的数量在每一轮都保持不变，而在这里你可以在每一轮改变堆的数量。 例如，如果我们执行 0101110 -> 0101010 最初我们有两堆大小为 1 和 3 但在移动之后我们将有 3 堆大小为 1。

Answer 1

让nim[n]是 n 序列的编号那些。然后我们有以下递推关系:

nim[n] = mex{nim[i] xor nim[j]: i, j >= 0, i + j < n}

(请参阅 Sprague-Grundy theorem 了解一般理论。)

从这个递归关系，你可以尝试计算序列nim的前几项，你会发现好像是nim[n] = n .

那么一个证明就很容易推导出来了，留给你吧。

---

因此 n 的序列consecutive ones 实际上相当于一个大小为 n 的 Nim 堆.现在很容易找到任何游戏的结果。

例如，如果我们有 0101110 , 则相当于两堆 Nim，大小为 1和 3分别。因此总数等于1 xor 3 = 2 ，它是非零的，所以第一个玩家获胜。

再举一个例子，如果我们有1110011111000111111 , 那么总数等于3 xor 5 xor 6 = 0 , 所以第一个玩家输了。

---

编辑:关于你关于堆的变化的问题，这里有更多的解释。

虽然桩数会有所变化，但重点在于:

• 如果一个状态的数字为零，则任何有效的移动都必须将其更改为非零数字状态。
• 如果一个状态的数量不为零，则必须存在一个有效的移动，将其更改为零数量状态。

因此对于获胜者来说，策略是将零状态留给对手。

示例:让我们从序列 1110011111000111111 开始，我用 3, 5, 6 表示简称。

如果第一个玩家替换了6乘以 2 的总和和 3 , 然后第二个玩家面临状态 3, 5, 1, 4 , 其中有编号 3 xor 5 xor 2 xor 3 = 7 .为了保持它的数量为零，第二个玩家替换了 5通过 2 , 离开第一个玩家 3, 2, 2, 3 ，它的数量又是零。

程序继续，直到第一个玩家没有有效的移动。