[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~m個石頭，兩個人交替拿，拿到最後一個的人獲勝。究竟是先手有利，還是後手有利？

 

1個石子，先手全部拿走；2個石子，先手全部拿走；3個石子，先手全部拿走；4個石子，後手面對的是先手的第1，2，3情況，後手必勝；5個石子，先手拿走1個讓後手面對第4種情況，後手必敗；6個石子，先手拿走2個讓後手面對第4種情況，後手必敗；…… 容易看出來，只有當出現了4的倍數，先手無可奈何，其余情況先手都可以獲勝。 （石子數量為4的倍數）後手的獲勝策略十分簡單，每次取石子的數量，與上一次先手取石子的數量和為4即可； （石子數量不為4的倍數）先手的獲勝策略也十分簡單，每次都令取之後剩余的石子數量為4的倍數（4*0=0，直接拿光），他就處於後手的位置上，利用上一行的策略獲勝。
代碼極為簡單：

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