0

我正在研究经典的硬币游戏问题：
Alice 和 Bob 正在使用一堆硬币玩游戏。玩家轮流从一堆硬币中挑选出几个硬币。每次允许玩家选择1、2或4个硬币，获得最后一个硬币的玩家为获胜者。爱丽丝选择了第一个。
我其实不明白结果是怎么来的。

    coinGame(1)= ('Alice', 1)
    coinGame(2) = ('Alice', 1)
    coinGame(3) = ('Bob', 2)
    coinGame(4) = ('Alice', 3)
    coinGame(5) = ('Alice', 2)
    coinGame(6) = ('Bob', 6)
    coinGame(7) = ('Alice', 8).

我了解 1,2,3...6 的输出，但不了解 7 及之后的输出。
对于输入 6，因为 Alice 总是会到达硬币 2、4 和 5。因此，Bob 只需选择 1、2 或 4 中的任何一个即可赢得比赛。总方式是 1 + 3 + 2 = 6 对于输入 7，Bob 可以达到 3 和 6，那么 Alice 只需选择 4 或 1 个硬币即可赢得游戏，其中 2 + 6 = 8 种获胜方式。我不明白的是，对于输入 7，Alice 也可以达到 5，然后 Bob 只需选择 2 即可获胜。为什么我们忽略了这个案例并认为 Alice 赢了？

我希望我能得到一些澄清。

谢谢！

4

1 回答 1

0

一个关键点
如果 Bob 赢得了比赛，那么有一些策略会让开始比赛的人松懈。
如果 Alice 赢了比赛，那么开始比赛的人就赢了。

因此，从每个 N 中检查 Bob 在 N-1、N-2 和 N-4 中是否有任何获胜位置。如果是，那么 Alice 将以 Bob 获胜的位置的总和获胜。

如果 Alice 从 N-1、N-2 和 N-4 中获胜，那么 Alice 肯定会从 N 中输掉这场比赛。
因为从 N-1、N-2 和 N-4 位置开始比赛的人正在赢得比赛。当 Alice 将轮到 Bob 时，Bob 将只得到 N-1、N-2 和 N-4 中的一个。从这些位置开始比赛的人将赢得比赛。

N>=5
sum=0
if Bob wins in N-1
    sum+=coinGame(N-1).count
if Bob wins in N-2
    sum+=coinGame(N-2).count
if Bob Wins in N-4 
    sum+=coinGame(N-4).count

if sum==0
   Bob wins with coinGame(N-1).count + coinGame(N-2).count + coinGame(N-4).count
else
   Alice wins with sum

找到 coinGame(7)
给定 coinGame(3) = ('Bob', 2) 7-4
coinGame(5) = ('Alice', 2) 7-2
coinGame(6) = ('Bob', 6) 7- 1

Bob 在 6 和 3 中以 6 计数
赢得比赛，所以 Alice 将从 7 以 8 赢得比赛

于 2019-10-21T08:37:18.157 回答