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.


一個拿石子的游戲，有n個石子，每次可以從中拿走[1,3]個。你和另一個人輪流拿石子，你先拿。
問：對於數量為n的石子，能否判斷你必勝？




思路：
如果有4個石子，輪到誰誰就輸了；
有8個石子，輪到誰誰也輸，因為我無論拿幾個，對方都會有辦法給我剩4個；
以此類推，有4k個石子，輪到誰誰輸。


而由於我先拿，因此只要第一次我能保證給對方剩余4的倍數個石子，我就能贏。
這樣就等於把這個拿石子問題轉化為了判斷n是否為4的倍數的問題。


因此代碼很簡單：

 public bool CanWinNim(int n) {
        if(n < 4){
    		return true;
    	}
    	
    	return n % 4 != 0;
    }