树搜索算法:如何快速确定A是否有一定的双赢策略

Question

原来的问题是这样的:有99块石头，A和B在玩一个游戏，每个人轮流拿一些石头，每个回合只能拿1，2，4或6块石头，最后一块石头赢。如果A是第一个取石的，那么在第一个转弯时，A要取多少块石头？

这似乎是一个相当复杂的树搜索测试，列出所有的分支，然后自下而上地工作:A取最后一块石头的叶子被标记为"win"；对于中间节点，无论B可能采取什么策略，如果A总是有一种方法到达标记为"win“的节点，这个节点也被标记为"win”。

但这种方法很费时。有什么聪明的算法来检验A是否有“保证赢”的策略？

Answer 1

O(n)溶液

如果我们先从1，2，4或6开始，A总是会赢的，因为他只会在第一步就把他们全部拿下。

如果我们从3开始，无论A做什么，他都会输，因为无论他是1还是2，B接下来都会赢。

如果我们从5开始，A将以2先发制人的方式获胜，从而将B送至上面的情况，在那里他以3块石头开始。

如果我们从7开始，A将通过使用4来获胜，并将B发送到与3相同的情况。

如果我们从8开始，不管A做了什么，他都会输:不管他拿什么，他都会把B送上一个制胜的位置。

如果我们从9开始，A可以取1，然后用8发送B到情况，导致他输掉。

如果我们从10开始，A可以选择2，然后再用8发送B，导致他输掉。

到目前为止，您应该已经非常清楚如何逐步构建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没有一个肯定的获胜策略。

Answer 2

好的，我们可以看到：

每次可取石数小于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，所以这个问题可以在O(1)中通过找到前56个数的结果来解决。