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.
尼姆游戲：有一堆石子，每次只能從里面拿出1~3塊。誰(shuí)拿到了最后一塊誰(shuí)贏。你先拿。兩個(gè)人都很聰明，都知道怎樣能贏。設(shè)計(jì)一個(gè)函數(shù)檢測(cè)對(duì)于給定的石子數(shù)，你能否贏得比賽。
算法分析：
方法一：
如果最后剩下4個(gè)石子，后拿的那個(gè)人贏。因此如果是4的倍數(shù)，你先拿x，后拿的人取4-x，因此后拿的那個(gè)人贏。
Java代碼
public class Solution {
public boolean canWinNim(int n) {
if (n % 4 == 0) return false;
else return true;
}
}
方法二
與方法一類(lèi)似，通過(guò)移位來(lái)判定是否是4的倍數(shù)，不是，就能贏。
Java代碼
public class Solution {
public boolean canWinNim(int n) {
if (n <= 0) return false;
return n>>2<<2 != n;
}
}
