292.Nim游戏

发表于 更新于 分类于 ，

题目

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4 输出: false 解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路

根据题目所说,我们每次可以拿1-3块,也就是说假设现在轮到我们的局面只剩1-3块,那我们必赢;但是如果轮到我们局面剩下4块,那我们必输,因为我们不管最后拿多少,肯定会剩下石头,让对手胜出,由此可见,在谁的回合中剩下4块石头,谁必输;另一方面,为了让对手回合有4块石头,我们的回合就一定得是5-7块石头,如果我们的回合有8块石头,那无论我们拿多少个石头,对方都能够逼迫我们下一回合拥有4块石头,所以我们也输了.

也就是说,只要我们的回合是4,8,12,16等等4的倍数块,那对手就总能够逼迫我们剩下四块,导致我们失败;另一方面,只要我们的回合不是4的倍数块,我们就能逼迫对手变成4的倍数块,从而赢得胜利.

代码

1
2
3
4
public bool CanWinNim(int n)
{
    return n % 4 != 0;
}