algorithm - 接近模数使用的算法

Question

我正在做一些编码挑战，出现了一个问题，大致是这样的:

"Two players each taking turns starting with player one. There are N sticks given, each player takes 1, 2 or 3 sticks on their turn, the player to take the last stick loses, the goal is to find an algorithm that lets player one win with certainty (not always possible, player two is supposed to take turns that will ensure victory) and output 1, 2 or 3 as the starting amount of sticks taken or 0 if it's impossible to win. Input is N. Example: Input:2 Output:1"

我试着考虑一下，但我想到的是它需要检查每一个可能的结果，因为如果 N 很大，所有的可能性都可以链接在一起。我还认为，如果玩家 2 拿走最后一根棍子以免输，那就是玩家 1 拿走 N-1(无论是只拿 N-1 还是拿 N-1、N-2 或 N- 1, N-2, N-3) 把N留给玩家2，只有这样才能确保胜利。原来解决方案是 (N-1) mod 4，但我不明白为什么会这样。

所以我的问题是你如何处理这样的问题，为什么解是模数？也有办法发现像这样的模数问题吗？其他编码员做得相当快，所以我想熟能生巧，但我不知道从哪里开始。

Answer 1

它是模 4 因为如果一个玩家有优势，如果第一个玩家拿了 1 个，他可以拿 3 根棍子，如果第一个玩家拿了 2 个，他拿 2 个，如果第一个玩家拿了 3 个，他可以拿 1 个棍子来保持同样的优势。另一个玩家根本没有任何控制权。

把问题倒过来:

你不必关心一个大N，你只需要分析当只剩下4根或更少的时候情况是什么样的。

当剩下 1、2、3 或 4 根棍子时，谁会获胜？

当剩下 4n+1、4n+2、4n+3 或 4n+4 根棍子时，谁会获胜？