gpt4 book ai didi

algorithm - Nim 的另一个游戏变体

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:01:09 25 4
gpt4 key购买 nike

给定N个二进制序列

例子:给定一个序列 101001 表示

玩家 0 只能选择一个元素为 0 的位置,并从该位置移除序列,结果{如果他选择第二个元素则为 1 或如果他选择第四个元素则为 101 或如果他选择第五个元素则为 1010}

玩家 1 只能选择一个有 1 个元素的位置,然后从该位置移除序列结果{如果他选择第一个元素则为 null 或如果他选择第三个元素则为 10 或如果他选择第 6 个元素则为 10100}

现在玩家 0 和玩家 1 轮流减少 N 个序列,每轮他们选择一个序列,选择一个元素并从该位置移除所选序列的末尾,如果玩家不能移动,他输了。

假设双方都发挥最佳,谁会赢?

我试图用 grundy 解决这个问题,但我无法将序列减少到 grundy 数字,因为这两个玩家没有相同的移动选项。谁能给我一个解决这个问题的提示?

顺便说一句,抱歉我的英语不好

最佳答案

这不是尼姆。这是Blue-red Hackenbush的游戏.甚至还有一个 online hackenbush calculator这可以解决这个特定的情况(只需将 B 和 R 更改为 0 和 1),以及对算法的简短解释:

Until a color change, each segment is worth +1 or -1 (depending on whether it is Blue or Red, respectively). Once a color change occurs, each subsequent segment (regardless of color), is worth half of the previous segment, with a +/- corresponding to the color. Thus, the string BBRB would be worth +1+1-1/2+1/4=7/4.

因此您可以计算每个序列的值。 (假设玩家 0 被分配到正面,即“0”的计算结果为 +1。)如果所有序列中这些值的总和为正,则玩家 0 获胜。如果为负,玩家 1 获胜。如果它是 0,那么谁先走就输。

关于algorithm - Nim 的另一个游戏变体,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19751649/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com