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.

二. 題目分析

題目的大意如下：

你正在和你的朋友們玩下面這個Nim游戲：有一堆石頭放在桌上，你每次可以從中拿走1到3顆。誰消除掉最後一個石頭即為贏家。假設你是第一輪開始取石頭。

現在你們游戲中的每個人都有著非常聰明的頭腦和絕佳的策略。寫一個函數，對與一個給定的石頭數目，算出你是否可以贏得這場比賽。

例如，如果石堆中有4顆石頭，那麼你永遠也無法贏得比賽：無論你移除了1、2或3顆石頭，最後1顆石頭都會被你的朋友所拿走。

更多關於Nim Game的解釋，可參照百科：http://baike.baidu.com/link?url=uxWV7mNdl-jkDWL6qj06zSX9Luvazbck4XqDo6IEcNgh2lNagWOmn7FyiN_YrjPHyaAyGeCF6yz2SwC-Irb2X_

其實對於這單一的問題，可以使用一行代碼解決。因為例子中當且僅當出現了4的倍數，先手必輸，其余情況先手都可以獲勝。

三. 示例代碼

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

四. 小結

這道題可以說毫無難度，但也可以經過適當變化，變成復雜的題目。