algorithm - 如果玩家最多可以拿走 4 个硬币，则赢得游戏的策略

Question

两个玩家正在玩一个游戏，每个玩家必须在每个回合中挑选 1、2、3 或 4 个硬币。一共有n个硬币。捡起最后一枚硬币的玩家获胜。设计赢得比赛的策略。

假设我是玩家之一，解决问题的算法策略是什么，这样我就可以赢得游戏？

Answer 1

为前 10 场左右的比赛制作一张 table ；会有一个清晰的模式。如果有...

1 coin: take 1, you win
2 coins: take 2, you win
3 coins: take 3, you win
4 coins: take 4, you win
5 coins: you lose (whatever you choose, the opponent wins by rule 1-4)
6 coins: take 1, opponent loses by rule 5
7 coins: take 2, opponent loses by rule 5
...
10 coins: you lose (whatever you choose, the opponent wins by rule 6-9)
11 coins: take 1, opponent loses by rule 10
...

所以，你总是拿走 n % 5 个硬币，除非它是 0(如果它是 0，你会输掉对手的完美游戏不管你做什么，所以拿 1 来最大化他犯错误的机会)。