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.

思路:很簡(jiǎn)單(之前大一acm宣講時(shí)大神提過的問題,然而并沒有什么卵用),每個(gè)人每次只能拿1,2或3塊石頭,最小是1,最大是3.也就是說下一個(gè)人一定可以(假設(shè)說兩人足夠聰明)根據(jù)上一個(gè)人拿的數(shù)量來湊出一個(gè)4.
結(jié)果很容易推演:甲先手取i塊,乙必定根據(jù)甲的情況取4-i塊,然后經(jīng)過n個(gè)回合(甲取,乙取),若還剩下石頭(少于4塊),則甲最后取完,甲勝.否則不剩下石頭,乙最后取完,乙勝.
歸根結(jié)底就是看總數(shù)是否是4的倍數(shù).

bool canWinNim(int n) {
    if (n%4 ==0) return false;
    else return true;
}