FB新题求解答

大家的验证算法都很棒，只是我一直在想真正的稳赢算法是怎么样的，我能推出5个洞以内的稳赢策略，可是6个洞以上怎么搞？
马尔科夫链的转移矩阵可以解决吗？

有可能有稳赢的吗？就算一个一个扫过去，那马云也可能藏在你旁边的山洞，然后下一天跟你调换位置，所以也会错过啊

lancelot981 发表于 2016-2-5 11:50
有可能有稳赢的吗？就算一个一个扫过去，那马云也可能藏在你旁边的山洞，然后下一天跟你调换位置，所以也会 ...

如果是5个或5个以内，可以利用他在最左或最右时，一定会往中间走的确定性获得稳赢策略。5个以上我目前想不到策略

有没有大神讨论一下？

我有个很笨的办法，就是可以列出numCaves=n的时候所有的可能性(6*2^(n-1)种)，然后loop这些可能性与strategy比较，每一个可能性都至少有一个元素与strategy在相同index处的值相同，那么就是必赢的情况，只要遇到一个可能性不属于这种情况，那就return false。

这个题是验证给定的策略正不争取， 所以应该没有这么难吧。采用minmax的策略。
对某一天， 要假设现在猜的位置是错误的， 然后根据在当前天数可能出现的格子情况， 得到下一天可能出现的位置， 如果可能出现的位置正好只为一个， 而策略中又正好猜对， 那么就一定能够捉到小偷。 反之， 如果不假设“当前猜的位置是错误的话”， 那么小偷就已经被捉到了。