树搜索算法：如何快速判断A是否有必胜策略
Tree searching algorithm: how to determine quickly if A has a sure-to-win strategy
原题是这样的：有99颗石子，A和B在玩一个游戏，每人轮流取一些石子，每轮只能取1,2,4,6个石子，拿走最后一块石头的人获胜。如果A是第一个拿石头的人，那么第一回合A应该拿多少石头？
这似乎是一个相当复杂的树搜索测验，列出所有分支，然后自下而上：A 拿走最后一块石头的叶子标记为 "win"；对于B可能采取的任何策略的中间节点，如果A总是有办法到达标记为"win"的节点，则该节点也标记为"win".
但是这种方法非常耗时。有什么智能算法可以检查 A 是否有 "guaranteed to win" 策略？
O(n)解
如果我们从 1、2、4 或 6 个石子开始，A 将永远获胜，因为他会在第一步中将它们全部拿走。
如果我们从3开始，A无论他做什么都会输，因为不管他拿1还是2，B接下来会拿2或1然后赢。
如果我们从 5 开始，A 将先拿 2 来获胜，从而将 B 发送到上面的情况，他从 3 石头开始。
如果我们从 7 开始，A 将取 4 获胜，将 B 发送到与 3 相同的情况。
如果我们从 8 开始，A 无论他做什么都会输：无论他拿什么，他都会将 B 送到获胜的位置。
如果我们从9开始，A可以拿1然后把B送到8的情况，导致他输。
如果我们从10开始，A可以拿2然后再把B送到8的情况，让他输。
到现在，如何逐步构建 O(n) 解决方案应该变得非常明显：令 win[i] = true if i stones are winnable for the first person to move
我们有：
win[1] = win[2] = win[4] = win[5] = win[6] = true, win[3] = false
win[x > 6] = not (win[x - 6] and win[x - 4] and win[x - 2] and win[x - 1])
例如：
win[7] = not (win[1] and win[3] and win[5] and win[6])
= not (true and false and true and true)
= not false
= true
一直计算到您感兴趣的数字，仅此而已。不涉及树木。
O(1)解
仔细看上面的解法，我们可以推导出一个简单的常数时间解法：注意A不管他做什么，只有在他把B送到赢位的情况下才会输，所以如果 k - 6, k - 4, k - 2, k - 1 都是获胜位置。
如果您为几个值计算 win，则模式变得明显：
win[k] = false if k = 3, 8, 11, 16, 19, 24, 27, 32...
=> win[k] = false iff k mod 8 == 3 or k mod 8 == 0
对于99，99 mod 8 = 3，所以A没有必胜之策。
好的，所以我们可以看到：
每一回合可以取的石子数量小于7，所以结果应该与模7有关。
所以，对于n < 1000，我打印出先手获胜的石子数的顺序，模数7，真正的重复循环。
1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5
这个循环的长度是56，所以这个问题可以通过找到前56个数字的结果在O(1)中解决。
原题是这样的：有99颗石子，A和B在玩一个游戏，每人轮流取一些石子，每轮只能取1,2,4,6个石子，拿走最后一块石头的人获胜。如果A是第一个拿石头的人，那么第一回合A应该拿多少石头？
这似乎是一个相当复杂的树搜索测验，列出所有分支，然后自下而上：A 拿走最后一块石头的叶子标记为 "win"；对于B可能采取的任何策略的中间节点，如果A总是有办法到达标记为"win"的节点，则该节点也标记为"win".
但是这种方法非常耗时。有什么智能算法可以检查 A 是否有 "guaranteed to win" 策略？
O(n)解
如果我们从 1、2、4 或 6 个石子开始，A 将永远获胜，因为他会在第一步中将它们全部拿走。
如果我们从3开始，A无论他做什么都会输，因为不管他拿1还是2，B接下来会拿2或1然后赢。
如果我们从 5 开始，A 将先拿 2 来获胜，从而将 B 发送到上面的情况，他从 3 石头开始。
如果我们从 7 开始，A 将取 4 获胜，将 B 发送到与 3 相同的情况。
如果我们从 8 开始，A 无论他做什么都会输：无论他拿什么，他都会将 B 送到获胜的位置。
如果我们从9开始，A可以拿1然后把B送到8的情况，导致他输。
如果我们从10开始，A可以拿2然后再把B送到8的情况，让他输。
到现在，如何逐步构建 O(n) 解决方案应该变得非常明显：令 win[i] = true if i stones are winnable for the first person to move
我们有：
win[1] = win[2] = win[4] = win[5] = win[6] = true, win[3] = false
win[x > 6] = not (win[x - 6] and win[x - 4] and win[x - 2] and win[x - 1])
例如：
win[7] = not (win[1] and win[3] and win[5] and win[6])
= not (true and false and true and true)
= not false
= true
一直计算到您感兴趣的数字，仅此而已。不涉及树木。
O(1)解
仔细看上面的解法，我们可以推导出一个简单的常数时间解法：注意A不管他做什么，只有在他把B送到赢位的情况下才会输，所以如果 k - 6, k - 4, k - 2, k - 1 都是获胜位置。
如果您为几个值计算 win，则模式变得明显：
win[k] = false if k = 3, 8, 11, 16, 19, 24, 27, 32...
=> win[k] = false iff k mod 8 == 3 or k mod 8 == 0
对于99，99 mod 8 = 3，所以A没有必胜之策。
好的，所以我们可以看到：
每一回合可以取的石子数量小于7，所以结果应该与模7有关。
所以，对于n < 1000，我打印出先手获胜的石子数的顺序，模数7，真正的重复循环。
1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5
这个循环的长度是56，所以这个问题可以通过找到前56个数字的结果在O(1)中解决。