当先锋百科网

首页 1 2 3 4 5 6 7

一    Nim游戏

一    Nim游戏

这一题很有意思,作为我们这篇博客的开头非常好,因为它会立刻让你对这类题产生兴趣

我一开始先想了想,1-3肯定先手赢,4后手赢,5-7先手赢,8后手赢,找规律吗?然后就找到了4的倍数后手赢

其实这题的规律是通过两个状态构成的

1-3不用说

5-7为啥先手一定会赢,因为先手在拿完第一次后,一定会让后手进入剩下4个的局面,我们知道剩下4个的局面时,谁先拿谁输

5的时候,先手拿1,后手剩4;6的时候,先手拿2,后手剩4;7的时候,先手拿3,后手拿4

而8的时候,无论先手拿几,后手拿完后总会让先手面对剩余4个的情况,所以8也是后手必赢的局面,因此往后都可以归结到4的倍数上后手必赢。

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