leetcode Nim Game

leetcode Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

题目地址： leetcode Nim Game

题意:

Nim游戏，n个石头，两个玩家轮流玩，每次只能拿掉1个或者2个或者3块石头，直到不能拿的一方算输。

现在给定石头个数n，求先拿者是否会赢得这个游戏？

思路:

简单的博弈论题。

下面的讨论对先拿者而言：

因为一次可以拿1~3个石头，所以n=1 ，2，3时候是必胜状态，因为你一次可以拿完。

而4是必败状态，因为你第一次无论拿几块，对手都可以一次拿完。（你拿1块，对手拿3个；你拿2块，对手拿2块；你拿3块，对手拿1块）

而5，6，7则是必胜状态，因为你一次可以拿到剩下4个，让对手进入必败状态。

同理，8是必败状态，无论拿几个，对手都进入了5，6，7的必胜状态.....

9，10，11必胜，因为可以拿到剩下8块给对手,12为必败.......

总结：能被4整除的必败，否则必胜。

代码很简单，一行搞定

C++

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Python

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 !=0